Short Term Strategies for a Dynamic Multi-Period Routing Problem

We consider a Dynamic Multi-Period Routing Problem (DMPRP) faced by a company which deals with on-line pickup 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.