A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows
- 1 June 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 46 (3), 330-335
- https://doi.org/10.1287/opre.46.3.330
Abstract
This article describes a generalized insertion heuristic for the Traveling Salesman Problem with Time Windows in which the objective is the minimization of travel times. The algorithm gradually builds a route by inserting at each step a vertex in its neighbourhood on the current route, and performing a local reoptimization. This is done while checking the feasibility of the remaining part of the route. Backtracking is sometimes necessary. Once a feasible route has been determined, an attempt is made to improve it by applying a post-optimization phase based on the successive removal and reinsertion of all vertices. Tests performed on 375 instances indicate that the proposed heuristic compares very well with alternative methods and very often produces optimal or near-optimal solutions.Keywords
This publication has 14 references indexed in Scilit:
- The Vehicle Routing Problem with Time Windows Part I: Tabu SearchINFORMS Journal on Computing, 1996
- An Optimal Algorithm for the Traveling Salesman Problem with Time WindowsOperations Research, 1995
- A Tabu Search Heuristic for the Vehicle Routing ProblemManagement Science, 1994
- A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windowsNetworks, 1993
- New Insertion and Postoptimization Procedures for the Traveling Salesman ProblemOperations Research, 1992
- A New Optimization Algorithm for the Vehicle Routing Problem with Time WindowsOperations Research, 1992
- A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time WindowsAmerican Journal of Mathematical and Management Sciences, 1986
- Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman ProblemOperations Research, 1983
- State‐space relaxation procedures for the computation of bounds to routing problemsNetworks, 1981
- A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride ProblemTransportation Science, 1980