A rolling horizon procedure for dynamic pickup and delivery problem with time windows
Authors:
- 1 August 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2087-2091
Abstract
In this paper, the dynamic Pickup and Delivery Problem with Time Windows (PDPTW) is studied, in which requests from customers arrive continuously, vehicles may breakdown, and time windows of customers may change. It is an NP-hard problem and impossible to find the optimal solution in a reasonable short time. Therefore, the exact methods are too limited to tackle this dynamic problem and the heuristic method is the only way. Inspired by the rolling horizon optimization theory from predictive control, a periodic and event-driven rolling horizon procedure is proposed to deal with the dynamic PDPTW. Simulation results show that our method is suitable for solving this class of dynamic problems. Finally, the conclusion is offered and some directions for further research are indicated.Keywords
This publication has 12 references indexed in Scilit:
- A rolling window optimization method for large-scale WCDMA base stations planning problemEuropean Journal of Operational Research, 2007
- A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windowsComputers & Operations Research, 2006
- A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery serviceComputers & Operations Research, 2006
- Double-horizon based heuristics for the dynamic pickup and delivery problem with time windowsTransportation Research Part B: Methodological, 2004
- Rolling horizon procedures for the single machine deterministic total completion time scheduling problem with release datesAnnals of Operations Research, 1997
- A computer assistant for vehicle dispatching with learning capabilitiesAnnals of Operations Research, 1995
- A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectivesAnnals of Operations Research, 1995
- Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup timesInternational Journal of Production Research, 1994
- Limited lookahead policies in supervisory control of discrete event systemsIEEE Transactions on Automatic Control, 1992
- The pickup and delivery problem with time windowsEuropean Journal of Operational Research, 1991