Travelling salesman problem

Jump to: navigation, search
An optimal TSP tour through Germany’s 15 largest cities. It is the shortest among 43 589 145 600[1] possible tours visiting each city exactly once.

The Travelling Salesman Problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.



In the theory of computational complexity, the decision version of TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly.



William Rowan Hamilton





Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a scientific explanation for the apparent computational difficulty of finding optimal tours.

Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and other managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound.

In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2005, Cook and others computed an optimal tour through a 33,810-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are provably within 1% of optimal tour.


As a graph problem

Symmetric TSP with four cities

The TSP can be modelled as a graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path's distance is the edge's length. A TSP tour becomes a Hamiltonian cycle, and the optimal TSP tour is the shortest Hamiltonian cycle. Often, the model is a complete graph (i.e. an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

Asymmetric and symmetric


With metric distances

In the metric TSP the intercity distances satisfy the triangle inequality. This can be understood as “no shortcuts”, in the sense that the direct connection from A to B is never longer than the detour via C.

c_{ij} \le c_{ik} + c_{kj}

These edge lengths define a metric on the set of vertices. When the cities are viewed as points in the plane, many natural distance functions are metrics.

  • In the Euclidian TSP the distance between two cities is the Euclidean distance between the corresponding points.
  • In the maximum metric, the distance between two points is the maximum of the differences of their x- and y-coordinates.


Non-metric distances

Distance measures that do not satisfy the triangle inequality arise in many routing problems. For example, one mode of transportation, such as travel by airplane, may be faster, even though it covers a longer distance.

In its definition, the TSP does not allow cities to be visited twice, but many applications do not need this constraint. In such cases, a symmetric, non-metric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the inter-city distance c_{ij} is replaced by the shortest path between i and j in the original graph.

Related problems

  • The generalized travelling salesman problem deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city" from each "state". Also known as the "travelling politician problem". One application is encountered in ordering a solution to the cutting stock problem in order to minimise knife changes. Another is concerned with drilling in semiconductor manufacturing, see e.g. U.S. Patent 7,054,798. Surprisingly, Behzad and Modarres[6] demonstrated that the generalised travelling salesman problem can be transformed into a standard travelling salesman problem with the same number of cities, but a modified distance matrix.

Computing a solution

The traditional lines of attacking for the NP-hard problems are the following:


Computational complexity


Complexity of approximation

In the general case, finding a shortest travelling salesman tour is NPO-complete.[7] If the distance measure is a metric and symmetric, the problem becomes APX-complete and Christofides’s algorithm approximates it within 3/2.[8]

If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 7/6. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio 0.814 log n;[9] it is an open question if a constant factor approximation exists.

The corresponding maximization problem of finding the longest travelling salesman tour is approximable within 63/38.[10] If the distance function is symmetric, the longest tour can be approximated within 4/3 by a deterministic algorithm[11] and within (33+\epsilon)/25 by a randomised algorithm.[12]

Exact algorithms

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute force search). The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is an algorithm that solves the problem in time O(n^2 2^n)[13][14][15]

The dynamic programming solution requires exponential space. Using inclusion–exclusion, the problem can be solved in time within a polynomial factor of 2^n and polynomial space.[16][17]

Improving these time bounds seems to be difficult. For example, it is an open problem if there exists an exact algorithm for TSP that runs in time O(1.9999^n)

Other approaches include:

  • Implementations of branch-and-bound and problem-specific cut generation; this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see


In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using Concorde TSP Solver: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists. The computation took approximately 15.7 CPU years (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using Concorde TSP Solver, taking over 136 CPU years, see .

Heuristic and approximation algorithms


Several categories of heuristics are recognized.

Constructive heuristics

The nearest neighbour (NN) algorithm (or so-called greedy algorithm) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N cities randomly distributed on a plane, the algorithm averagely yields length = 1.25 * exact_shortest_length.



Recently a new constructive heuristic, Match Twice and Stitch (MTS) (Kahng, Reda 2004 [19]), has been proposed. MTS has been shown to empirically outperform all existing tour construction heuristics. MTS performs two sequential matchings, where the second matching is executed after deleting all the edges of the first matching, to yield a set of cycles. The cycles are then stitched to produce the final tour.

Iterative improvement

  • Pairwise exchange, or Lin–Kernighan heuristics.
The pairwise exchange or '2-opt' technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. This is a special case of the k-opt method. Note that the label 'Lin–Kernighan' is an often heard misnomer for 2-opt. Lin–Kernighan is actually a more general method.
  • k-opt heuristic
  • V-opt heuristic

Randomised improvement

  • Random path change algorithms are currently the state-of-the-art search algorithms and work up to 100,000 cities. The concept is quite simple: Choose a random path, choose four nearby points, swap their ways to create a new random path, while in parallel decreasing the upper bound of the path length. If repeated until a certain number of trials of random path changes fail due to the upper bound, one has found a local minimum with high probability, and further it is a global minimum with high probability[citation needed] (where high means that the rest probability decreases exponentially in the size of the problem - thus for 10,000 or more nodes, the chances of failure is negligible).

TSP is a touchstone for many general heuristics devised for combinatorial optimization such as genetic algorithms, simulated annealing, Tabu search, ant colony optimization, and the cross entropy method.

Example: Using inversion to find an approximate solution

While David Goldberg wrote about this method in terms of DNA[20], it is repeated here in terms of a travelling salesman. This method shortens the path by opening loops at random. After all the loops are opened, one final loop remains that defines a perimeter. While a perimeter is not always the optimal path, it is usually very close. In a special case when all towns are equidistantly placed along a circle, the perimeter is the optimal solution.

Suppose a salesman has a deck of 60 cards, each with the location of a different town. He wants to find the optimal path by arranging the cards, calculating the length, and comparing results over and over. If the hometown is not counted, then the number of possible permutations becomes 60*59*58*...*4*3 or 4.2×1081. This is more than the estimated number of atoms in the observable universe! With this method, he likely won't find the optimal path or even get close before dying of old age.

Using inversion instead, the salesman starts with the shuffled cards laid out in front of him. First, he calculates the path length. Then he randomly picks four contiguous cards and inverts their order (i.e. A B C D -> D C B A). After recalculating the path length, he keeps the new order if it is shorter as in the figure below with 6 towns (note: the hometown, point 1, is not counted).


For 60 towns, a loop is randomly opened more than once in every 602 attempts. If the salesman has a friend with an identical card deck, then they can double their chances of opening a loop. They both lay out the cards in the same order, then randomly select different sets of four cards to invert. Naturally, more friends working in parallel will continue to improve the odds. The figure below shows a randomly generated path connecting 60 points.


Each iteration has 180 parallel inversion operations (i.e. friends), 60 of which are combined to make a new path. After about 1500 iterations, all loops have been opened, reducing the tour to 1/5 of the original length. See figure below.


Out of 4.2×1081 possible permutations, the inversion method found an approximately optimal path with 180*1500 = 2.7×105 random inversion operations.

Ant colony optimization

Artificial intelligence researcher Marco Dorigo described in 1997 a method of heuristically generating "good solutions" to the TSP using a simulation of an ant colony called ACS (Ant Colony System).[21] It uses some of the same ideas used by real ants to find short paths between food sources and their nest, an emergent behaviour resulting from each ant's preference to follow trail pheromones deposited by other ants.


Aco TSP.svg

Special cases

Metric TSP

A very natural restriction of the TSP is to require that the distances between cities form a metric, i.e., they satisfy the triangle inequality. That is, for any 3 cities A, B and C, the distance between A and C must be at most the distance from A to B plus the distance from B to C. Most natural instances of TSP satisfy this constraint.

In this case, there is a constant-factor approximation algorithm due to Christofides[22] that always finds a tour of length at most 1.5 times the shortest tour. In the next paragraphs, we explain a weaker (but simpler) algorithm which finds a tour of length at most twice the shortest tour.


  • Construct the minimum spanning tree.
  • Find a Eulerian cycle in it. Clearly, its length is twice the length of the tree.



In the special case that distances between cities are all either one or two (and thus the triangle inequality is necessarily satisfied), there is a polynomial-time approximation algorithm that finds a tour of length at most 8/7 times the optimal tour length.[23] However, it is a long-standing (since 1975) open problem to improve the Christofides approximation factor of 1.5 for general metric TSP to a smaller constant. It is known that, unless P = NP, there is no polynomial-time algorithm that finds a tour of length at most 220/219=1.00456… times the optimal tour's length.[24] In the case of bounded metrics it is known that there is no polynomial time algorithm that constructs a tour of length at most 1/388 more than optimal, unless P = NP.[25]

Euclidean TSP



In general, for any c > 0, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in O(n (log n)^O(c)) time; this is called a polynomial-time approximation scheme[26] In practice, heuristics with weaker guarantees continue to be used.

Asymmetric TSP


Solving by conversion to Symmetric TSP

Solving an asymmetric TSP graph can be somewhat complex. The following is a 3x3 matrix containing all possible path weights between the nodes A, B and C. One option is to turn an asymmetric matrix of size N into a symmetric matrix of size 2N, doubling the complexity.

Asymmetric Path Weights
A 1 2
B 6 3
C 5 4

To double the size, each of the nodes in the graph is duplicated, creating a second ghost node. Using duplicate points with very low weights, such as -∞, provides a cheap route "linking" back to the real node and allowing symmetric evaluation to continue. The original 3x3 matrix shown above is visible in the bottom left and the inverse of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by -∞.

Symmetric Path Weights
A B C A' B' C'
A -∞ 6 5
B 1 -∞ 4
C 2 3 -∞
A' -∞ 1 2
B' 6 -∞ 3
C' 5 4 -∞

The original 3x3 matrix would produce two Hamiltonian cycles (a path that visits every node once), namely A-B-C-A [score 9] and A-C-B-A [score 12]. Evaluating the 6x6 symmetric version of the same problem now produces many paths, including A-A'-B-B'-C-C'-A, A-B'-C-A'-A, A-A'-B-C'-A [all score 9-∞].

The important thing about each new sequence is that there will be an alternation between dashed (A',B',C') and un-dashed nodes (A,B,C) and that the link to "jump" between any related pair (A-A') is effectively free. A version of the algorithm could use any weight for the A-A' path, as long as that weight is lower than all other path weights present in the graph. As the path weight to "jump" must effectively be "free", the value zero (0) could be used to represent this cost — if zero is not being used for another purpose already (such as designating invalid paths). In the two examples above, non-existent paths between nodes are shown as a blank square.



Human performance on TSP

The TSP, in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It is observed that humans are able to produce good quality solutions quickly. The first issue of the Journal of Problem Solving is devoted to the topic of human performance on TSP.

TSP path length for random pointset in a square

Consider N points randomly distributed in a 1 x 1 square with N>>1.

It is known that, for N points in a unit square, the TSP always has length at most proportional to the square root of N, and that random pointset will have length at least proportional to the square root. However, the constants of proportionality, both for worst-case pointset and for random pointset, are unknown yet.

Lower bound

A lower bound of the shortest tour length is \frac{1}{2} \sqrt{N}, obtained by assuming i be a point in the tour sequence and i has its nearest neighbor as its next in the tour. [27]

A better lower bound is \left({\frac{1}{4} + \frac{3}{8}}\right)\sqrt{N}, obtained by assuming i's next is i's nearest, and i's previous is i's second nearest.

Divide tour sequence into 2 parts as before_i and after_i with each part contains N/2 points. Delete before_i points from the square to build a diluted environment. Now the best next point that i can find in after_i part is \sqrt{\frac{1}{2N}} away. This leads to a lower bound \sqrt{\frac{N}{2}}.

  • David S. Johnson[28] obtained a lower bound by computer experiment:

0.7080\sqrt{N}+0.522 , where 0.522 comes from the points near square boundary which have fewer neighbors.

  • Christine L. Valenzuela and Antonia J. Jones [29] obtained another lower bound by computer experiment:


Upper bound

By applying simulated annealing method on samples of N=40000, computer shows an upper bound

\left(\sqrt{\frac{N}{2}}+0.72\right) \cdot 1.015 , where 0.72 comes from boundary effect.

Because the actual solution is only the shortest path, for the purposes of programmatic search another upper bound is the length of any previously discovered approximation.

See also

  • Canadian traveller problem
  • Vehicle routing problem
  • Route inspection problem
  • Set TSP problem
  • Seven Bridges of Königsberg
  • Six degrees of separation
  • Traveling repairman problem (minimum latency problem)
  • Traveling tourist problem


  1. Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43 589 145 600
  2. “Der Handlungsreisende – wie er sein soll und was er zu thun [sic] hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur”
  3. A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 1736-1936
  7. Orponen, P.; Mannila, H. (1987), "On approximation preserving reductions: Complete problems and robust measures'", Technical Report C-1987-28, Department of Computer Science, University of Helsinki.
  9. Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", In Proc. 44th IEEE Symp. on Foundations of Comput. Sci., pp. 56–65.
  10. Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), "Long tours and short superstrings'", Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 166–177.
  12. Hassin, R.; Rubinstein, S. (2000), "Better approximations for max TSP", Information Processing Letters 75: 181–186.
  13. Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", in Bellman, R., Hall, M., Jr. (eds.), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, pp. 217–249.
  16. Kohn, S.; Gottlieb, A.; Kohn, M. (1977), "A Generating Function Approach to the Traveling Salesman Problem", ACM Annual Conference, ACM Press, pp. 294–300.
  17. Karp, R.M. (1982), "Dynamic programming meets the principle of inclusion and exclusion", Oper. Res. Lett. 1: 49–51, doi:10.1016/0167-6377(82)90044-X.
  18. Work by David Applegate, AT&T Labs - Research, Robert Bixby, ILOG and Rice University, Vašek Chvátal, Concordia University, William Cook, Georgia Tech, and Keld Helsgaun, Roskilde University is discussed on their project web page hosted by Georgia Tech and last updated in June 2004, here
  20. Goldberg, David E: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Pub. Co. 1989. ISBN: 0201157675
  22. N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
  23. P. Berman (2006). M. Karpinski, "8/7-Approximation Algorithm for (1,2)-TSP", Proc. 17th ACM-SIAM SODA (2006), pp. 641-648.
  24. C.H. Papadimitriou and Santosh Vempala. (2000). "On the approximability of the traveling salesman problem", Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  25. L. Engebretsen, M. Karpinski, Approximation hardness of TSP with bounded metrics, Proceedings of 28th ICALP (2001), LNCS 2076, Springer 2001, pp. 201-212.
  26. Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. Journal of the ACM, Vol.45, Issue 5, pp.753–782. ISSN:0004-5411. September 1998.
  27. Lingwanjae talk
  28. David S. Johnson
  29. Christine L. Valenzuela and Antonia J. Jones


  • Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook (2006), The Traveling Salesman Problem 
  • Christofides, N. (1976), "Worst-case analysis of a new heuristic for the travelling salesman problem", Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh. 

Further reading

  • Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W. J. (2006), The Traveling Salesman Problem: A Computational Study, Princeton University Press, ISBN 978-0-691-12993-8 .
  • Cook, William; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computing with domino-parity inequalities for the TSP", INFORMS Journal on Computing 19 (3): 356–365, doi:10.1287/ijoc.1060.0204 .
  • Goldberg, D. E. (1989), Genetic Algorithms in Search, Optimization & Machine Learning, New York: Addison-Wesley .
  • Gutin, G.; Yeo, A.; Zverovich, A. (2002), "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP", Discrete Applied Mathematics 117 (1–3): 81–86, doi:10.1016/S0166-218X(01)00195-0 .
  • Gutin, G.; Punnen, A. P. (2006), The Traveling Salesman Problem and Its Variations, Springer, ISBN 0-387-44459-9 .
  • Johnson, D. S.; McGeoch, L. A. (1997), "The Traveling Salesman Problem: A Case Study in Local Optimization", in Aarts, E. H. L.; Lenstra, J. K., Local Search in Combinatorial Optimisation, John Wiley and Sons Ltd, pp. 215–310 .
  • Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9 .
  • Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M., II (1977), "An Analysis of Several Heuristics for the Traveling Salesman Problem", SIAM Journal on Computing 6 (5): 563–581, doi:10.1137/0206041 .
  • Vickers, D.; Butavicius, M.; Lee, M.; Medvedev, A. (2001), "Human performance on visually presented traveling salesman problems", Psychological Research 65: 34–45 .
  • Walshaw, Chris (2000), A Multilevel Approach to the Travelling Salesman Problem, CMS Press .
  • Walshaw, Chris (2001), A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem, CMS Press .

External links

  • Traveling Salesman Problem by Jon McLoone based on a program by Stephen Wolfram, after work by Stan Wagon, Wolfram Demonstrations Project.