Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems
- 1 August 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 38 (3), 369-378
- https://doi.org/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(n3). However, straightforward implementations of handling complicating constraints lead to an undesirable time complexity of O(n4). We demonstrate that with careful implementation it is possible, in most cases, to maintain the O(n3) complexity or, in a few cases, increase the time complexity to O(n3 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
This publication has 10 references indexed in Scilit:
- The Vehicle Routing ProblemPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002
- A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhaulingJournal of the Operational Research Society, 1999
- The fleet size and mix vehicle routing problem with time windowsJournal of the Operational Research Society, 1999
- The Vehicle Routing Problem with Time Windows Part II: Genetic SearchINFORMS Journal on Computing, 1996
- A heuristic algorithm for the asymmetric capacitated vehicle routing problemEuropean Journal of Operational Research, 1996
- A parallel route building algorithm for the vehicle routing and scheduling problem with time windowsEuropean Journal of Operational Research, 1993
- Inventory/routing: Reduction from an annual to a short-period problemNaval Research Logistics (NRL), 1987
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window ConstraintsOperations Research, 1987
- A computational comparison of algorithms for the inventory routing problemAnnals of Operations Research, 1985
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977