TY - JOUR
T1 - Short Term Strategies for a Dynamic Multi-Period Routing Problem
AU - Angelelli, E.
AU - Bianchessi, N.
AU - Mansini, R.
AU - Speranza, M. G.
PY - 2009/1/1
Y1 - 2009/1/1
N2 - 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.
AB - 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.
KW - Dynamic Multi-Period Routing Problems
KW - Postponable requests
KW - Short Term Strategies
UR - http://www.scopus.com/inward/record.url?scp=61349088732&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=61349088732&partnerID=8YFLogxK
U2 - 10.1016/j.trc.2008.02.001
DO - 10.1016/j.trc.2008.02.001
M3 - Article
AN - SCOPUS:61349088732
SN - 0968-090X
VL - 17
SP - 106
EP - 119
JO - Transportation Research. Part C, Emerging Technologies
JF - Transportation Research. Part C, Emerging Technologies
IS - 2
ER -