A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows

Michel Gendreau, Alain Hertz, Gilbert Laporte and Mihnea Stan
Additional contact information
Michel Gendreau: Université de Montrél, Montréal, Québec, Canada
Alain Hertz: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Gilbert Laporte: École des Hautes Études Commerciales, Montreál, Québec, Canada
Mihnea Stan: Delta Technology, Atlanta, Georgia

Operations Research, 1998, vol. 46, issue 3, 330-335

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: Traveling salesman problem with time windows; generalized insertion heuristic (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.330 (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:oropre:v:46:y:1998:i:3:p:330-335

Access Statistics for this article

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