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:

• Is the graph unweighted? - If the graph is unweighted, or all the edges have one of two cost values, the problem reduces to finding a Hamiltonian cycle.   See Section for a discussion of this problem.
• Are you given as input n points or a weighted graph? - Geometric points are often easier to work with than a graph representation, for several reasons.   First, they define a complete graph, so there is never an issue of finding a tour, just a good one. Second, although we always could construct the complete distance graph on the points and feed it to a graph solver, it might be more efficient to construct a sparse nearest-neighbor graph (see Section ) and work primarily from that. Finally, geometric instances inherently satisfy the triangle inequality, discussed below.   
• How important is the restriction against visiting each vertex more than once? - The restriction that the tour not revisit any vertex may be important in certain applications, but it often is irrelevant. For example, the cheapest way to visit all vertices might involve repeatedly visiting a hub site, as is common in modern air travel.  

  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.

• How important is that that you find the optimal tour? - If you insist on solving your TSP to optimality (and you probably shouldn't bother), there are two common approaches.   Cutting plane methods model the problem as an integer program, then solve the linear programming relaxation of it.   If the optimal solution is not at integer points, additional constraints designed to force integrality are added. Branch-and-bound algorithms perform a combinatorial search while maintaining   careful upper and lower bounds on the cost of a tour or partial tour. In the hands of professionals, problems with thousands of vertices can be solved. In the hands of one gleaning their knowledge from this book, problems with 50 to maybe 100 vertices are potentially solvable, using the implementations discussed below.

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:

• Minimum spanning trees - A simple and popular heuristic, especially when the sites represent points in the plane, is based on the minimum spanning tree of the points.   By doing a depth-first search of this tree, we walk over each edge of the tree exactly twice, once going down when we discover the new vertex and once going up when we backtrack. We can then define a tour of the vertices according to the order in which they were discovered and use the shortest path between each neighboring pair of vertices in this order to connect them. This path must be a single edge if the graph is complete and obeys the triangle inequality, as with points in the plane. As discussed in Section , the resulting tour is always at most twice the length of the minimum TSP tour. In practice, it is usually better, typically 15% to 20% over optimal. Further, the time of the algorithm is bounded by that of computing the minimum spanning tree, only in the case of points in the plane (see Section ).  
• Incremental insertion methods -   A different class of heuristics inserts new points into a partial tour one at a time (starting from a single vertex) until the tour is complete.   The version of this heuristic that seems to work best is furthest point insertion: of all remaining points, insert the point v into partial tour T such that

  

  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.

• k-optimal tours - Substantially more powerful are the Kernighan-Lin, or k-opt class of heuristics. Starting from an arbitrary tour, the method applies local refinements to the tour in the hopes of improving it. In particular, subsets of edges are deleted from the tour and the k remaining subchains rewired in a different way to see if the resulting tour is an improvement. A tour is k-optimal when no subset of k edges can be deleted and rewired so as to reduce the cost of the tour. Extensive experiments suggest that 3-optimal tours are usually within a few percent of the cost of optimal tours. For k > 3, the computation time increases considerably faster than solution quality. Two-opting a tour is a fast and effective way to improve any other heuristic.   Simulated annealing provides an alternate mechanism to employ edge flips to improve heuristic tours.   

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 ).