Article ID: | iaor20071803 |
Country: | United Kingdom |
Volume: | 33 |
Issue: | 4 |
Start Page Number: | 875 |
End Page Number: | 893 |
Publication Date: | Apr 2006 |
Journal: | Computers and Operations Research |
Authors: | Hentenryck Pascal Van, Bent Russell |
Keywords: | optimization: simulated annealing, heuristics |
This paper presents a two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows and multiple vehicles (PDPTW). The first stage uses a simple simulated annealing algorithm to decrease the number of routes, while the second stage uses Large neighborhood search (LNS) to decrease total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems with 100, 200, and 600 customers. In particular, it has improved 47% and 76% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing. They also answer positively the open issue in the original LNS paper, which advocated the use of LNS for the PDPTW and argue for the robustness of LNS with respect to side-constraints.