Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems

Ann Melissa Campbell () and Martin Savelsbergh ()
Additional contact information
Ann Melissa Campbell: Department of Management Sciences, Henry B. Tippie College of Business, University of Iowa, Iowa City, Iowa 52242-1000
Martin Savelsbergh: Department of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205

Transportation Science, 2004, vol. 38, issue 3, 369-378

Abstract: 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 3 ). However, straightforward implementations of handling complicating constraints lead to an undesirable time complexity of O ( n 4 ). We demonstrate that with careful implementation it is possible, in most cases, to maintain the O ( n 3 ) complexity or, in a few cases, increase the time complexity to O ( n 3 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.

Keywords: vehicle routing and scheduling; insertion heuristics; time windows; variable delivery times; shifts (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (56)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0046 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:38:y:2004:i:3:p:369-378

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().