Main Page | See live article | Alphabetical index

Traveling salesman problem

The traveling salesman problem (TSP), also known as the traveling salesperson problem, is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory.

The problem can be stated as: Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city and then returns to the starting city?

An equivalent formulation in terms of graph theory is: Find the shortest Hamiltonian cycle in a weighted graph.

A related problem is the Bottleneck traveling salesman problem (bottleneck TSP): Find the Hamiltonian cycle in a weighted graph with the minimal length of the longest edge.

Table of contents
1 Computational complexity
2 Algorithms
3 External Links

Computational complexity

The most direct solution would be to try all the combinations and see which one is cheapest, but given that the number of combinations is N! (the factorial of the number of cities), this solution rapidly becomes impractical.

The problem has been shown to be NP-hard, and the decision version of it ("given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NP-complete.

The bottleneck TSP is also NP-hard.

The problem is of considerable practical importance, for example in printed circuit assembly automation, where holes or component locations play the part of cities. Various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. An approximative solution for 15,112 cities in Germany was found in 2001 by Princeton University scholars.


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

Exact algorithms


Special cases

TSP with triangle inequality

Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. The problem stii remains NP-hard, however many heuristics work better. It turns out that the instrumental property in this case is the triangle inequality.

The length of the minimum spanning tree of the network is a natural lower bound for the length of the optimal route. In the TSP with triangle inequality case it as possible to prove upper bounds in terms of the minimum spanning tree and design an algorithm that has provable upper bound on the length of the route. The first published (and the simplest) example follows.

It is easy to prove that the last step works. Moreover, thanks to the triangle inequality, each skipping at Step 4 is in fact a shortcut, i.e., the length of the cycle do not incease. Hence it gives us the TSP tour no more than twice as slong as the optimal one.

Better implementations of this heuristic are known, as well as other heuristics with better worst case estimates.

See also:

External Links