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. Articles by Gendreau, M. Search for Related Content

Vehicle Routing Problem with Time Windows, Part II: Metaheuristics

Agora Innoroad Laboratory, University of Jyväskylä, P. O. Box 35, FIN-40014 Jyväskylä, Finland
Département d’informatique et de recherche opérationelle, and Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Canada H3C 3J7
olli.braysy{at}jyu.fi
michelg{at}crt.umontreal.ca

This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in the first part of this article. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed.

Key Words: vehicle routing; time windows; heuristics; metaheuristics; tabu search; genetic algorithms
History: Received: December 2001; revised: December 2002; accepted: December 2002.

This article has been cited by other articles:

				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]

				G. Desaulniers, F. Lessard, and A. Hadjar Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows Transportation Science, August 1, 2008; 42(3): 387 - 404. [Abstract] [PDF]

				J. W. Ohlmann, M. J. Fry, and B. W. Thomas Route Design for Lean Production Systems Transportation Science, August 1, 2008; 42(3): 352 - 370. [Abstract] [PDF]

				S. Irnich A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics INFORMS Journal on Computing, January 1, 2008; 20(2): 270 - 287. [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]