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 I: Route Construction and Local Search Algorithms

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 presents a survey of the research on 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. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solomon’s benchmark test problems are presented and analyzed. Moreover, we discuss how heuristic methods should be evaluated and propose using the concept of Pareto optimality in the comparison of different heuristic approaches. The metaheuristic methods are described in the second part of this article.

Key Words: vehicle routing; time windows; heuristics; local search 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]

				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]