Bräysy, O., Hasle, G. and Dullaert, W. (2004). A multi-start local search algorithm for the vehicle routing problem with time windows European Journal of Operational Research, 159(3):586--605.
-
Affiliated author
-
Publication year2004
-
JournalEuropean Journal of Operational Research
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 MSLS 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.