TRAVELING SALESMAN PROBLEM

The traveling salesman problem (TSP), also known as the traveling salesperson problem, 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?

The most direct answer 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.

How fast are the best known deterministic algorithms?

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

Algorithms

The first algorithm used to solve the traveling salesman problem is the nearest neighbour algorithm, which is normally fairly close to the optimal route, and doesn't take too long to execute. Upper and lower bounds for the length of the optimal route can be found using the minimum spanning tree of the network.

Another algorithm is an insertion algorithm, the Dakin branch-and-bound algorithm, which can be used to process TSPs containing 40-60 cities.

Yet another, progressive improvement algorithm which uses techniques reminiscent of linear programming works well up to 120-200 cities.

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.

However, the only way to be completely confident of finding the optimal route is to check every route, which is completely impractical for TSPs with more than 25-30 cities.

See also:

• Tabu search

External Links

• http://www.math.princeton.edu/tsp/index.html (Princeton University TSP page)
• http://www.pcug.org.au/~dakin/tsp.htm (private web page with 2 algorithms & demo program to download)
• http://cs.felk.cvut.cz/~xobitko/ga/tspexample.html (Example of finding approximate solution of TSP problem using Genetic algorithm)