next up previous contents index CD CD Algorithms
Next: Hamiltonian Cycle Up: Graph Problems: Hard Problems Previous: Vertex Cover

Traveling Salesman Problem



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:

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:

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   See Section gif.

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 tex2html_wrap_inline29388 algorith or by e-mailing Chad Hurrwitz at A heuristic Euclidean TSP solver in C due to Lionnel Maugis is available from tex2html_wrap_inline29390 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 gif.

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 gif for details.     

XTango (see Section gif) 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 gif.

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 tex2html_wrap_inline29394 , where the bottleneck is the time it takes to find a minimum-weight perfect matching (see Section gif).   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 tex2html_wrap_inline29396 factor approximations in polynomial time for any tex2html_wrap_inline29398 . 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 gif), which can be computed in tex2html_wrap_inline29400 time. Other easy special cases are known.

Related Problems: Hamiltonian cycle (see page gif), minimum spanning tree (see page gif), convex hull (see page gif).      

next up previous contents index CD CD Algorithms
Next: Hamiltonian Cycle Up: Graph Problems: Hard Problems Previous: Vertex Cover

Mon Jun 2 23:33:50 EDT 1997