A multi-start local search algorithm for the vehicle routing problem with time windows

Olli Bräysy*, Geir Hasle, Wout Dullaert

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


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.

Original languageEnglish
Pages (from-to)586-605
Number of pages20
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 16 Dec 2004


  • Metaheuristics
  • Routing
  • Time windows

Cite this