Traveling salesman problem

Problem statement

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.

It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.

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.

The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classical example is in printed circuit manufacturing -- scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem).

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.

Algorithms

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

• Devising algorithms for finding exact solutions (they will work reasonably fast only for relatively small problem sizes)
• Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver seemingly or provably good solutions, but which could not proved to be optimal.
• Finding special cases for the problem ("subproblems") for which either exact or better heuristics are posible.

For benchmarking of TSP algorithms, TSPLIB a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits.

Exact algorithms

• Various branch and bound algorithms, which can be used to process TSPs containing 40-60 cities.
• Progressive improvement algorithms which use techniques reminiscent of linear programming works well up to 120-200 cities.

An exact solution for 15,112 Germany cities from TSPLIB was found in 2001 using the Cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer Johnson in 1954, based on linear programming. The computations were performed on a network of 110 processors located at Rice University and Princeton University, see the Princeton external link. The total computation time was 22.6 years (scaled to a single 500 MHz Alpha processor).

Heuristics

Various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are provably 2-3% away from the optimal solution.

Several categories of heuristics are recognized.

Constructive heuristics

• The nearest neighbour algorithm, which is normally fairly close to the optimal route, and doesn't take too long to execute. Unfortunately it is can be provably reliable only for special cases of the TSP. In general case, however there exists an example for which the nearest neighbour algorithm gives the worst possible route.

Iterative improvement

• Pairwise exchange, or Kernighan-Lin heuristics.

Randomized improvement

• Optimised Markov chain algorithms which utilise local searching heuristical sub-algorithms can find a route extremely close to the optimal route for 700-800 cities.

TSP is a touchstone for many general heuristics devised for combinatorial optimization: genetic algorithms, simulated annealing, Tabu search, neural nets.

Special cases

Restricted locations

• A trivial special case is when all cities are located on the perimeter of a convex polygon.
• A good exercise in combinatorial algorithms is to solve the TSP for a set of cities located along the two concentric circles.

TSP with triangle inequality

Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. The problem still 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 is possible to prove upper bounds in terms of the minimum spanning tree and design an algorithm that has a provable upper bound on the length of the route. The first published (and the simplest) example follows.

• Step 1: Construct the minimal spanning tree.
• Step 2: Duplicate all its edges. This gives us an Eulerian graph.
• Step 3: Find an Eulerian cycle in it. Clearly, its length is twice the length of the tree.
• Step 4: Convert the Eulerian cycle into the Hamiltonian one in the following way: walk along the Eulerian cycle, and each time you are about to come into an already visited vertex, skip it and try to go to the next one (along the Eulerian cycle).

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 increase. Hence it gives us a TSP tour no more than twice as long as the optimal one.

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

References

• G. B. Dantzig, R. Fulkerson, and S. M. Johnson, Solution of a large-scale traveling salesman problem, Operations Research 2 (1954), 393-410.

Related articles

• Tabu search
• Assignment problem

External Links

• TSPLIB
• Princeton University TSP page
• Private web page with 2 algorithms & demo program to download
• Example of finding approximate solution of TSP problem using a genetic algorithm

Referenced By