Introduction

The traveling salesman problem (TSP) has commanded much attention from mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is c ij ) and then return to the home city, what is the least costly route the traveling salesman can take? A complete historical development of this and related problems can be found in Hoffman and Wolfe (1985), Applegate et al. (2006), and Cook (2011).

The importance of the TSP is that it is representative of a larger class of problems known as combinatorial optimization problems. The TSP problem belongs in the class of such problems known as NP-complete. Specifically, if one can find an efficient (i.e., polynomial-time) algorithm for the traveling salesman problem, then efficient algorithms could be found for all other problems in the NP-complete class. To date, however, no one has found a polynomial-time algorithm for the TSP. Does that mean that it is impossible to solve any large instances of such problems? To the contrary, nowadays many practical optimization problems of truly large scale are solved to optimality routinely. From 1992 to 2006, Concorde, a software created by D. Applegate, R.E. Bixby, V. Chvátal, and W.J. Cook (Applegate et al. 1995, 2006), solved (among many others) a traveling salesman problem that models the production of printed circuit boards having 7,397 holes (cities), a problem over the 13,509 largest cities in the U.S., one over the 24,978 cities of Sweden, and, finally, a 85,900 city problem arising from a VLSI application. So, although the question of what it is that makes a problem difficult may remain open, the computational record of specific instances of TSP problems coming from practical applications is optimistic.

How are such problems tackled? Obviously, one cannot consider a brute-force approach. For example, for a 16-city traveling salesman problem, there are 653,837,184,000 distinct routes that would need to be evaluated. Rather than enumerating all possibilities, successful algorithms for solving the TSP problem eliminate most of the routes without ever explicitly considering them.

Formulations

The first step to solving instances of large TSPs must be to find a good mathematical formulation of the problem. In the case of the traveling salesman problem, the mathematical structure is a graph where each city is denoted by a point (or node) and lines are drawn connecting every two nodes (called arcs or edges). Associated with every line is a distance (or cost). When the salesman can get from every city to every other city directly, then the graph is said to be complete. A round-trip (route) of the cities corresponds to some subset of the lines, and is called a tour or a Hamiltonian cycle in graph theory. The length of a tour is the sum of the lengths of the lines in the round-trip.

Depending upon whether or not the direction in which an edge of the graph is traversed matters, one distinguishes the asymmetric from the symmetric traveling salesman problem. To formulate the asymmetric TSP on m cities, one introduces zero-one variables

$$ {x_{ij }} = \left\{ \begin{array}{ll} 1\,\,{\rm{if}\,\rm{the}\,\rm{edge} \, }i \to j\,{\rm{is}\,\rm{in}\,\rm{the}\,\rm{tour}}\, \cr0\,\,\rm{{ otherwise}}\cr\end{array} \right.$$

and, given the fact that every node of the graph must have exactly one edge pointing towards it and one pointing away from it, one obtains the classic assignment problem. These constraints alone are not enough since this formulation would allow subtours, i.e., it would allow disjoint loops to occur. For this reason, a proper formulation of the asymmetric traveling salesman problem must remove these subtours from consideration by the addition of subtour-elimination constraints. The problem then becomes

$$ \begin{array}{ll} & \min\,\,\,\sum\limits_{{j = 1}}^m{\sum\limits_{{i = 1}}^m {{c_{ij }}{x_{ij }}} } \hfill \cr &\mathrm{{\rm s}}{.\mathrm{\rm t}}{.}\,\,\,\,\,\sum\limits_{{j =1}}^m {{x_{ij }} = 1\,\,\,\mathrm{{\rm for}}\,i = 1,\,.\,.\,.,\,m}\hfill \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\sum\limits_{{j = 1}}^m{{x_{ij }} = 1\,\,\,\mathrm{{\rm for}}\,j = 1,\,.\,.\,.,\,m} \hfill\cr & \,\,\,\,\,\sum\limits_{{i\ \in\,K}} {\sum\limits_{{j\ \in\,K}}{{x_{ij }} \leq \left| K \right|} } - 1\,\,\mathrm{{for}}\,\mathrm{{\rm all}}\,K \subset \left\{ {1,\,.\,.\,., m}\right\}\,\,\,\, \hfill \cr \end{array} $$

where K is any nonempty proper subset of the cities 1, …, m. The cost c ij is allowed to be different from the cost c ji . Note that there are m(m − 1) 0–1 variables in this formulation.

To formulate the symmetric traveling salesman problem, one notes that the direction traversed is immaterial, so that c ij = c ji . Since direction does not now matter, one can consider the graph where there is only one arc (undirected) between every two nodes. Thus, let x j ∈ {0,1} be the decision variable where j runs through all edges E of the undirected graph and c j is the cost of traveling that edge. To find a tour in this graph, one must select a subset of edges such that every node is contained in exactly two of the edges selected. Thus, the problem can be formulated as a 2-matching problem in a graph having m(m − 1)/2 0–1 variables, that is, half of the number of the previous formulation. As in the asymmetric case, subtours must be eliminated through subtour elimination constraints. The problem can therefore be formulated as

$$\begin{array}{ll}&\min\,\,\,\,\,\left({1/2}\right)\sum\limits_{{j=1}}^m{\sum\limits_{{k\in{\ J_{(j)}}}}{c_k {x_k}}}\hfill\cr&\mathrm{{s}}{.\mathrm{t}}{.}\,\,\,\,\,\,\,\,\sum\limits_{{k\in{J_{(j)}}}}{x_k=2\,\,\,\mathrm{{for}}\,\,\mathrm{{all}}\,j=1,\,.\,.\,.,m}\hfill\cr&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\sum\limits_{{j\in\,\,E(K)}}{x_j\leq\left|K\right|}-1\,\,\,\mathrm{{for}}\,\mathrm{{all}}\,\,\,K\subset\,\left\{{1,\,.\,.\,.,m}\right\}\hfill\cr&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{x_j}=0\,or\,1\,\,\mathrm{{for}}\,\mathrm{{all}}\,jinE,\hfill\cr\end{array} $$

where J(j) is the set of all undirected edges connected to node j and E(K) is the subset of all undirected edges connecting the cities in any proper, nonempty subset K of all cities. Of course, the symmetric problem is a special case of the asymmetric one, but practical experience has shown that algorithms for the asymmetric problem perform, in general, badly on symmetric problems. Thus, the latter need a special formulation and solution treatment. In addition, as an ATSP instance can be easily turned into a symmetric one with twice the number of nodes, any algorithm for STSP can be used to solve an ATSP.

Algorithms

Exact approaches to solving such problems require algorithms that generate both a lower bound and an upper bound on the true minimum value of the problem instance. Any round-trip tour that goes through every city exactly once is a feasible solution with a given cost that cannot be smaller than the minimum cost tour. Algorithms that construct feasible solutions, and thus upper bounds for the optimum value, are called heuristics. These solution strategies produce answers but often without any quality guarantee as to how far off they may be from the optimal answer. Heuristic algorithms that find a feasible solution in a single attempt are called constructive heuristics, while algorithms that iteratively modify and try to improve some given starting solution are called improvement heuristics. When the solution one obtains is dependent on the initial starting point of the algorithm, the same algorithm can be used multiple times from various (random) starting points. Often, if one needs a solution quickly, one may settle for a well-designed heuristic algorithm that has been shown empirically to find near-optimal tours to many TSP problems. Research by Golden and Stewart (1985), Jünger, Reinelt and Rinaldi (1994), Johnson and McGeoch (2002), and Applegate et al. (2006) describes algorithms that find solutions to extremely large TSPs (problems with hundreds of thousands, or even millions of variables) to within 1 or 2% of optimality in very reasonable times. The heuristic algorithm of Lin and Kernighan appears so far to be the most effective in term of solution quality, in particular with the variant proposed by Helsgaun (2000), which was able to find, for the first time, the optimal solution (although without a quality guarantee) of several instances of TSPLIB, a well known library of TSP problems described in Reinelt (1991). For genetic algorithmic approaches to the TSP, see Potvin (1996); for simulated annealing approaches see Aarts, Korst and Laarhoven (1988); for neural net approaches, see Potvin (1993); for tabu search approaches, see Fiechter (1990); and for a very effective evolutionary algorithm, see Nagata (2006). Probabilistic analysis of heuristics are discussed in Karp and Steele (1985); performance guarantees for heuristics are given in Johnson and Papadimitriou (1985) and Arora (2002), where an amazing result concerning the polynomial-time approximability is described for Euclidean TSP instances (where the nodes are points in the plane and the traveling costs are the Euclidean distances between the points). For an analysis of the heuristics for the ATSP, see Johnson et al. (2002).

In order to know about the closeness of the upper bound to the optimum value, one must also know a lower bound on the optimum value. If the upper and lower bound coincide, a proof of optimality is achieved. If not, a conservative estimate of the true relative error of the upper bound is provided by the difference of the upper and the lower bound divided by the lower bound. Thus, one needs both upper and lower bounding techniques to find provably optimal solutions to hard combinatorial problems or even to obtain solutions meeting a quality guarantee.

So how does one obtain and improve the lower bound? A relaxation of an optimization problem is another optimization problem whose set of feasible solutions properly contains all feasible solution of the original problem and whose objective function value is less than or equal to the true objective function value for points feasible to the original problem. Thus, the true problem is replaced by one with a larger feasible region but that is more easily solvable. This relaxation is continually refined so as to tighten the feasible region so that it more closely represents the true problem. The standard technique for obtaining lower bounds on the TSP problem is to use a relaxation that is easier to solve than the original problem. These relaxations can have either discrete or continuous feasible sets. Several relaxations have been considered for the TSP. Among them are the n-path relaxation, the assignment relaxation, the 2-matching relaxation, the 1-tree relaxation, and the linear programming relaxation. For randomly generated asymmetric TSPs, problems having up to 7,500 cities have been solved, in the early 1990s, using an assignment relaxation which adds subtours within a branch and bound framework and which uses an upper bounding heuristic based on subtour patching, (Miller and Pekny 1991). For the symmetric TSP, the 1-tree relaxation and the 2-matching relaxations have been most successful. These relaxations have been embedded into a branch-and-bound framework.

The process of finding constraints that are violated by a given relaxation is called a cutting plane technique and all successes for large TSP problems have used cutting planes to continuously tighten the formulation of the problem. To obtain a tight relaxation the inequalities utilized as cutting planes in many computational approaches to the TSP are often facet-defining inequalities.

One of the simplest classes of cuts that have been shown to define facets of the underlying TSP polytope is the subtour elimination cut. Besides these constraints, comb inequalities, clique tree inequalities, path, wheelbarrow and bicycle inequalities, ladder, crown, domino and many other inequalities have also been shown to define facets of this polytope. The underlying theory of facet generation for the symmetric traveling salesman problem is provided in Grötschel and Padberg (1985), Jünger, Reinelt and Rinaldi (1994) and Naddef (2002); analogous results for the ATSP polytope are provided in Balas and Fischetti (2002). The algorithmic descriptions of how these inequalities are used in cutting plane approaches are discussed in Padberg and Rinaldi (1991), in Jünger, Reinelt and Rinaldi (1994), and in Applegate et al. (2006) where it is also shown how the polynomial-time equivalence between optimization and separation can be turned into a powerful algorithmic tool to generate inequalities not necessarily belonging to one of the known types.

Cutting plane procedures can then be embedded into a tree search in an algorithmic framework referred to as branch and cut and proposed in Padberg and Rinaldi (1991), where it is shown how such approach made it possible to solve some still unsolved instances of sizes up to 2,392 nodes. Some of the largest TSP problems solved have used parallel processing to assist in the search for optimality. This is the case of the software Concorde, where all the known algorithmic ideas for the TSP (and many new ones) have been carefully implemented. With this code, Applegate et al. (2006) managed to solve all problems of the TSPLIB to optimality; for the largest one, of 85,900 nodes, they used 96 workstations for a total of 139 years of CPU time.

As understanding of the underlying mathematical structure of the TSP problem improves, and with the continuing advancement in computer technology, it is likely that many difficult and important combinatorial optimization problems will be solved using a combination of cutting plane generation procedures, heuristics, variable fixing through logical implications and reduced costs, and tree search.

Applications

One might ask, however, whether the TSP problem is important enough to have received all of the attention it has. Much of the attention that the problem has received is because it is a relatively simple problem to describe and yet a difficult (from a complexity viewpoint) optimization problem to solve. However, there are important cases of practical problems that can be formulated as TSP problems and many other problems are generalizations of this problem. Besides the drilling of printed circuits boards described above, problems having the TSP structure occur in the analysis of the structure of crystals (Bland and Shallcross 1987), in the overhauling of gas turbine engines (Pante et al. 1987), in material handling in a warehouse (Ratliff and Rosenthal 1981), in cutting stock problems (Garfinkel, 1977), in the clustering of data arrays (Lenstra and Rinooy Kan 1975), in the sequencing of jobs on a single machine (Gilmore and Gomory 1964), in the assignment of routes for planes of a specified fleet (Boland et al. 1994) and in genome sequencing (Ben-Dor and Chor 1997; Ben-Dor et al. 2000). Related variations on the traveling salesman problem include the resource-constrained traveling salesman problem, which has applications in scheduling with an aggregate deadline (Pekny and Miller 1991). This paper also shows how the prize collecting traveling salesman problem (Balas 2002) and the orienteering problem (Golden et al. 1987; Fischetti et al. 2002) are special cases of the resource constrained TSP. Most importantly, the traveling salesman problem often comes up as a subproblem in more complex combinatorial problems, perhaps the best-known application being the vehicle routing problem. This is the problem of determining for a fleet of vehicles which customers should be served by each vehicle and in what order each vehicle should visit the customers assigned to it. For relevant surveys, see Christofides (1985), Fisher (1987), and the book The Vehicle Routing Problem, edited by Toth and Vigo (2001).

Concluding Remarks

The seminal paper on the TSP is Dantzig, Fulkerson and Johnson (1954). Books by Lawler et al. (1985), Reinelt (1994) and Gutin and Punnen (2002), and the survey and annotated bibliography by Jünger, Reinelt and Rinaldi (1994, 1997), summarize most of the research up through 2002 and provide extensive references. For a deep understanding of how algorithms for TSP work, see the book by Applegate et al. (2006), which besides providing a wide overview on TSP history and on its applications, also gives a detailed description of how all the components of the Concorde software are built: a valuable source for algorithm designers. Finally, the book by Cook (2011) is for a more general audience, requiring almost no mathematical background to read, but very nicely and completely describing the TSP from several interesting viewpoints. The computer program Concorde, the TSPLIB, and many other sources of information on the TSP are available electronically at a Web site that can be easily located through Web search.

See

Assignment Problem

Branch and Bound

Chinese Postman Problem

Integer and Combinatorial Optimization

Combinatorics

Computational Complexity

Graph Theory

Heuristics

Linear Programming

Network

NP, NP-Complete, NP-Hard

Tabu Search