INFORMS Journal on Computing · 1992 · 469 citations · 0 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsCombinatorial OptimizationGeometric ApproximationGeometric OptimizationHeuristic SearchNearest Neighbor SearchDistance MetricsTraveling Salesman ApproximationTraveling Salesman ProblemTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
The paper presents efficient algorithms for approximating traveling salesman tours in multidimensional point sets. The authors implement a suite of starting heuristics (e.g., Nearest Neighbor, Farthest Insertion) and local optimizations (2‑Opt, 3‑Opt) that work across various distance metrics and dimensions. Experiments show the algorithms run in O(N log N) time on uniform data, remain fast on highly nonuniform data, and can solve million‑city planar TSP instances to within a few percent of optimal in a few CPU hours. Published in INFORMS Journal on Computing (ISSN 1091‑9856), formerly ORSA Journal on Computing (1989‑1995, ISSN 0899‑1499).
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.