On dynamic pickup and delivery vehicle routing with several time windows and waiting times

In 2001, Caramia and his coauthors introduced a very fast and efficient heuristic for rooting a fleet of vehicles for dynamic combined pickup and delivery services [Caramia, M., Italiano, G.F., Oriolo, G., Pacifici, A., Perugia, A., 2001. Routing a fleet of vehicles for dynamic combined pickup and delivery services. In: Proceedings of the Symposium on Operation Research 2001, Springer-Verlag, Berlin/Heidelberg, pp. 3–8.]. The authors assume that every client names a stretch-factor that denotes the maximal relative deviation from the shortest path between pickup and delivery point. Waiting times are not allowed. As these assumptions are not very realistic, this paper now presents the results of adapting this algorithm to the dynamic pickup and delivery vehicle routing problem with several time windows. Waiting times of vehicles are admitted. Moreover, the computational results are considerably improved by local search techniques making use of free computational capacity.