Article ID: | iaor2007205 |
Country: | United States |
Volume: | 15 |
Issue: | 4 |
Start Page Number: | 347 |
End Page Number: | 368 |
Publication Date: | Sep 2003 |
Journal: | INFORMS Journal On Computing |
Authors: | Brysy Olli |
Keywords: | heuristics |
The purpose of this paper is to present a new deterministic metaheuristic based on a modification of the variable neighborhood search of Mladenovic & Hansen for solving the vehicle-routing problem with time windows. Results are reported for the standard 100, 200, and 400 customer data sets by Solomon and Gehring & Homberger, and two real-life problems by Russell. The findings indicate that the proposed procedure outperforms other recent local searches and metaheuristics. In addition, four new best-known solutions were obtained. The proposed procedure is based on a new four-phase approach. In this approach an initial solution is first created using new route-construction heuristics followed by a route-elimination procedure to improve the solutions regarding the number of vehicles. In the third phase the solutions are improved in terms of total traveled distance using four new local-search procedures proposed in this paper. Finally, in phase four, the best solution obtained is improved by modifying the objective function to escape from a local minimum.