Abstract
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 language | English |
|---|---|
| Pages (from-to) | 586-605 |
| Number of pages | 20 |
| Journal | European Journal of Operational Research |
| Volume | 159 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 16 Dec 2004 |
Keywords
- Metaheuristics
- Routing
- Time windows
