Input description: A weighted graph G.
Problem description: Find the cycle of minimum cost that visits each of the vertices of G exactly once.
Discussion: The traveling salesman problem is the most notorious NP-complete problem. This is a function of its general usefulness, and because it is easy to explain to the public at large. Imagine a traveling salesman who has to visit each of a given set of cities by car. What is the shortest route that will enable him to do so and return home, thus minimizing his total driving?
Although the problem arises in transportation applications, its most important applications arise in optimizing the tool paths for manufacturing equipment. For example, consider a robot arm assigned to solder all the connections on a printed circuit board. The shortest tour that visits each solder point exactly once defines the most efficient path for the robot. A similar application arises in minimizing the amount of time taken by a graphics plotter to draw a given figure.
Several issues arise in solving TSPs:
This issue does not arise whenever the graph observes the triangle inequality; that is, for all vertices , . In graphs that observe the triangle inequality, the shortest tour visits each vertex once. Heuristics work much better on graphs that do obey the triangle inequality.
Almost any flavor of TSP is going to be NP-complete, so the right way to proceed is with heuristics. These are often quite successful, typically coming within a few percent of the optimal solution, which is close enough for engineering work. Unfortunately, there have been literally dozens of heuristics proposed for TSPs, so the situation can be confusing. Empirical results in the literature are sometime contradictory. However, we recommend choosing from among the following heuristics:
The minimum ensures that we insert the vertex in the position that adds the smallest amount of distance to the tour, while the maximum ensures that we pick the worst such vertex first. This seems to work well because it first ``roughs out'' a partial tour before filling in details. Typically, such tours are only 5% to 10% longer than optimal.
Implementations: The world-record-setting traveling salesman program is by Applegate, Bixby, Chvatal, and Cook [ABCC95], which has solved instances as large as 7,397 vertices to optimality. At this time, the program is not being distributed. However, the authors seem willing to use it to solve TSPs sent to them. In their paper, they describe this work as neither theory nor practice, but sport - an almost recreational endeavor designed principally to break records. It is a very impressive piece of work, however.
The TSPLIB library of test instances for the traveling salesman problem is available from Netlib, and by anonymous ftp from softlib.cs.rice.edu. See Section .
Tsp_solve is a C++ code by Chad Hurwitz and Robert Craig that provides both heuristic and optimal solutions. Geometric problems of size up to 100 points are manageable. It is available from http://www.cs.sunysb.edu/ algorith or by e-mailing Chad Hurrwitz at churritz@crash.cts.com. A heuristic Euclidean TSP solver in C due to Lionnel Maugis is available from http://www.cenaath.cena.dgac.fr/ maugis/tsp.shar.
Pascal implementations of branch-and-bound search and the insertion and Kerighan-Lin heuristics (for 2-opt and 3-opt) appear in [SDK83]. For details, see Section .
Algorithm 608 [Wes83] of the Collected Algorithms of the ACM is a Fortran implementation of a heuristic for the quadratic assignment problem, a more general problem that includes the traveling salesman as a special case. Algorithm 750 [CDT95] is a Fortran code for the exact solution of asymmetric TSP instances. See Section for details.
XTango (see Section ) includes animations of both the minimum spanning tree heuristic and a genetic algorithm for TSP. The latter converges sufficiently slowly to kill one's interest in genetic algorithms.
Combinatorica [Ski90] provides (slow) Mathematica implementations of exact and approximate TSP solutions. See Section .
Notes: The definitive reference on the traveling salesman problem is the book by Lawler et. al. [LLKS85]. Experimental results on heuristic methods for solving large TSPs include [Ben92a, GBDS80, Rei94]. Typically, it is possible to get within a few percent of optimal with such methods. TSPLIB [Rei91] provides the standard collection of hard instances of TSPs that arise in practice.
The Christofides heuristic is an improvement of the minimum-spanning tree heuristic and guarantees a tour whose cost is at most 3/2 times optimal on Euclidean graphs. It runs in , where the bottleneck is the time it takes to find a minimum-weight perfect matching (see Section ). Good expositions of the Christofides heuristic [Chr76] include [Man89, PS85]. Expositions of the minimum spanning tree heuristic [RSL77] include [CLR90, O'R94, PS85].
Polynomial-time approximation schemes for Euclidean TSP have been recently developed by Arora [Aro96] and Mitchell [Mit96], which offer factor approximations in polynomial time for any . They are of great theoretical interest, although any practical consequences remain to be determined.
The history of progress on optimal TSP solutions is somewhat inspiring. In 1954, Dantzig, Fulkerson, and Johnson solved a symmetric TSP instance of 42 United States cities [DFJ54]. In 1980, Padberg and Hong solved an instance on 318 vertices [PH80]. Applegate et. al. [ABCC95] have recently solved problems that are twenty times larger than this. Some of this increase is due to improved hardware, but most is due to better algorithms. The rate of growth demonstrates that exact solutions to NP-complete problems can be obtained for large instances if the stakes are high enough. Unfortunately, they seldom are. Good expositions on branch-and-bound methods include [PS82, SDK83]. Good expositions of the Kernighan-Lin heuristic [LK73, Lin65] include [MS91, PS82, SDK83].
Size is not the only criterion for hardness. One can easily construct an enormous graph consisting of one cheap cycle, for which it would be easy to find the optimal solution. For sets of points in convex position in the plane, the minimum TSP tour is described by its convex hull (see Section ), which can be computed in time. Other easy special cases are known.
Related Problems: Hamiltonian cycle (see page ), minimum spanning tree (see page ), convex hull (see page ).