Short Term Strategies for a Dynamic Multi-Period Routing Problem

E. Angelelli*, N. Bianchessi, R. Mansini, M. G. Speranza

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review


    We consider a Dynamic Multi-Period Routing Problem (DMPRP) faced by a company which deals with on-line pick-up requests and has to serve them by a fleet of uncapacitated vehicles over a finite time horizon. When a request is issued, a deadline of a given number of days d ≤ 2 is associated to it: if d = 1 the request has to be satisfied on the same day (unpostponable request) while if d = 2 the request may be served either on the same day or on the day after (postponable request). At the beginning of each day some requests are already known, while others may arrive as time goes on. Every day the company faces on-line requests by possibly making new plans for the service and decides whether or not to serve postponable requests without knowing the set of new requests that will be issued the day after. The company objective is to satisfy all the received requests while minimizing the average operational costs per day. The daily cost includes a very high cost paid for each request forwarded to a back-up service. We propose different short term routing strategies and analyze their impact on the long term objective. Extensive computational results are provided on randomly generated instances simulating different real case scenarios and conclusions are drawn on the effectiveness of the strategies.

    Original languageEnglish
    Pages (from-to)106-119
    Number of pages14
    JournalTransportation Research. Part C, Emerging Technologies
    Issue number2
    Publication statusPublished - 1 Jan 2009


    • Dynamic Multi-Period Routing Problems
    • Postponable requests
    • Short Term Strategies


    Dive into the research topics of 'Short Term Strategies for a Dynamic Multi-Period Routing Problem'. Together they form a unique fingerprint.

    Cite this