This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bräysy, O. Search for Related Content

A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows

Department of Optimization, SINTEF Applied Mathematics, P.O. Box 124 Blindern, N-0314 Oslo, Norway
Olli.Braysy{at}math.sintef.no

The purpose of this paper is to present a new deterministic metaheuristic based on a modification of the variable neighborhood search of Mladenovic and Hansen (1997) for solving the vehicle-routing problem with time windows. Results are reported for the standard 100, 200, and 400 customer data sets by Solomon (1987) and Gehring and Homberger (1999), and two real-life problems by Russell (1995). 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.

Key words: Metaheuristics; Vehicle Routing; Time Windows
History: received June 2001; revised December 2001; accepted May 2002.

This article has been cited by other articles:

				J.-Y. Potvin State-of-the Art Review--Evolutionary Algorithms for Vehicle Routing INFORMS Journal on Computing, October 1, 2009; 21(4): 518 - 548. [Abstract] [PDF]

				V. Schmid, K. F. Doerner, R. F. Hartl, M. W. P. Savelsbergh, and W. Stoecher A Hybrid Solution Approach for Ready-Mixed Concrete Delivery Transportation Science, February 1, 2009; 43(1): 70 - 85. [Abstract] [PDF]

				O. Braysy, W. Dullaert, G. Hasle, D. Mester, and M. Gendreau An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows Transportation Science, August 1, 2008; 42(3): 371 - 386. [Abstract] [PDF]

				A. Lim and X. Zhang A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows INFORMS Journal on Computing, January 1, 2007; 19(3): 443 - 457. [Abstract] [PDF]

				T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno, and M. Yagiura Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints Transportation Science, May 1, 2005; 39(2): 206 - 232. [Abstract] [PDF]

				O. Braysy and M. Gendreau Vehicle Routing Problem with Time Windows, Part II: Metaheuristics Transportation Science, February 1, 2005; 39(1): 119 - 139. [Abstract] [PDF]

				R. Bent and P. Van Hentenryck A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows Transportation Science, November 1, 2004; 38(4): 515 - 530. [Abstract] [PDF]