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.