We investigate the impact of two strategies for dynamic pickup and delivery problems on the quality of solutions produced by insertion heuristics: (a) a waiting strategy that delays the final assignment of vehicles to their next destination, and (b) a request buffering strategy that postpones the assignment of some non-urgent new requests to the next route planning. In this study, the strategies are tested in a constructive-deconstructive heuristic for the dynamic pickup and delivery problem with hard time windows and random travel times. Comparisons of the solution quality provided by these strategies to a more conventional approach were performed on randomly generated instances up to 100 requests with static and dynamic (time-dependent) travel times and different degrees of dynamism. The results indicate the advantages of the strategies both in terms of lost requests and number of vehicles.
https://doi.org/10.3138/infor.46.3.165Cite as:
@article{Pureza_2008,
doi = {10.3138/infor.46.3.165},
url = {https://doi.org/10.3138%2Finfor.46.3.165},
year = 2008,
month = {aug},
publisher = {Informa {UK} Limited},
volume = {46},
number = {3},
pages = {165--175},
author = {Vit{'{o}}ria Pureza and Gilbert Laporte},
title = {Waiting and Buffering Strategies for the Dynamic Pickup and Delivery Problem with Time Windows},
journal = {{INFOR}: Information Systems and Operational Research}
}