Journal article
Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems
Transportation science, Vol.38(3), pp.369-378
08/01/2004
DOI: 10.1287/trsc.1030.0046
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.
Details
- Title: Subtitle
- Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems
- Creators
- Ann Melissa Campbell - University of IowaMartin Savelsbergh - Georgia Institute of Technology
- Resource Type
- Journal article
- Publication Details
- Transportation science, Vol.38(3), pp.369-378
- DOI
- 10.1287/trsc.1030.0046
- ISSN
- 0041-1655
- eISSN
- 1526-5447
- Language
- English
- Date published
- 08/01/2004
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380432802771
Metrics
4 Record Views