Abstract
This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt). Experiments indicate that most of the algorithms run in O(N log N) time on uniform data sets, and many run almost as fast on very nonuniform data. The program that implements the algorithms is able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours. The algorithms and program apply to many distance metrics and dimensions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
Travelling salesman problemHeuristicsComputer scienceAlgorithmImplementationOperating system
Affiliated Institutions
Related Publications
State-of-the-Art Survey—The Traveling Salesman Problem: A Neural Network Perspective
This paper surveys the “neurally” inspired problem-solving approaches to the traveling salesman problem, namely, the Hopfield-Tank network, the elastic net, and the self-organiz...
Commentary—Progress in Linear Programming
There is little doubt that barrier methods are now indispensable tools in the solution of large-scale linear programming problems. However, it is our opinion that the results of...
On Finding Primal- and Dual-Optimal Bases
We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for on...
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
A survey of the significant developments in the field of interior point methods for linear programming is presented, beginning with Karmarkar's projective algorithm and concentr...
Commentary—Major Cholesky Would Feel Proud
Probably more than any other group, authors Lustig, Marsten, and Shanno have led the way in demonstrating the effectiveness of interior methods for solving large, real-world lin...
Publication Info
- Year
- 1992
- Type
- article
- Volume
- 4
- Issue
- 4
- Pages
- 387-411
- Citations
- 461
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
461
OpenAlex
Cite This
Jon Jouis Bentley
(1992).
Fast Algorithms for Geometric Traveling Salesman Problems.
INFORMS Journal on Computing
, 4
(4)
, 387-411.
https://doi.org/10.1287/ijoc.4.4.387
Identifiers
- DOI
- 10.1287/ijoc.4.4.387