Fast algorithms for geometric traveling salesman problems. (English) Zbl 0758.90071
Summary: 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.
MSC:
90C35 | Programming involving graphs or networks |
90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
90C27 | Combinatorial optimization |
90C06 | Large-scale problems in mathematical programming |