| Article ID: | iaor20052583 |
| Country: | Netherlands |
| Volume: | 159 |
| Issue: | 3 |
| Start Page Number: | 586 |
| End Page Number: | 605 |
| Publication Date: | Dec 2004 |
| Journal: | European Journal of Operational Research |
| Authors: | Hasle Geir, Brysy Olli, Dullaert Wout |
| Keywords: | heuristics |
In this paper a multi-start local search (MSLS) heuristic is proposed for the vehicle routing problem with time windows (VRPTW). In VRPTW the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified service time windows. The suggested approach is based on a MSLA framework and several new improvement heuristics. A new speedup technique is introduced for the construction heuristics, and the results of the MSLS are post-optimized by a threshold accepting post-processor. Experimental results on 358 benchmark problems from the literature show that the suggested method is highly efficient and competitive.