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

Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems

Department of Management Sciences, Henry B. Tippie College of Business, University of Iowa, Iowa City, Iowa 52242-1000
Department of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
ann-campbell{at}uiowa.edu
martin.savelsbergh{at}isye.gatech.edu

Insertion heuristics have proven to be popular methods for solving a variety of vehicle routing and scheduling problems. In this paper, we focus on the impact of incorporating complicating constraints on the efficiency of insertion heuristics. The basic insertion heuristic for the standard vehicle routing problem has a time complexity of O(n³). However, straightforward implementations of handling complicating constraints lead to an undesirable time complexity of O(n⁴). We demonstrate that with careful implementation it is possible, in most cases, to maintain the O(n³) complexity or, in a few cases, increase the time complexity to O(n³ log n). The complicating constraints we consider in this paper are time windows, shift time limits, variable delivery quantities, fixed and variable delivery times, and multiple routes per vehicle. Little attention has been given to some of these complexities (with time windows being the notable exception), which are common in practice and have a significant impact on the feasibility of a schedule as well as the efficiency of insertion heuristics.

Key Words: vehicle routing and scheduling; insertion heuristics; time windows; variable delivery times; shifts
History: Received: February 2002; revised: June 2002; accepted: June 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]

				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]

				A. M. Campbell, D. Vandenbussche, and W. Hermann Routing for Relief Efforts Transportation Science, May 1, 2008; 42(2): 127 - 145. [Abstract] [PDF]

				A. M. Campbell and M. Savelsbergh Incentive Schemes for Attended Home Delivery Services Transportation Science, August 1, 2006; 40(3): 327 - 341. [Abstract] [PDF]

				A. M. Campbell and M. W. P. Savelsbergh A Decomposition Approach for the Inventory-Routing Problem Transportation Science, November 1, 2004; 38(4): 488 - 502. [Abstract] [PDF]