Travelling salesman problem

The traveling salesman problem is a prominent illustration of a class of problems in computational complexity theory. The problem can be enounced 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 exactly once and then returns to the start city?

The most immediate 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 becomes rapidly unpractical.

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, and various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. An approximative solution for 15112 cities in Germany was found in 2001 by Princeton University scholars.

The main algorithm used to solve the traveling salesman problem is the nearest neighbour algorithm, which is normally fairly close to the optimal route. Upper and lower bounds for the length of the optimal route can be found using the minimum spanning tree of the network. 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 15-20 cities.

External related web sites:

• http://www.math.princeton.edu/tsp/index.html (Princeton University TSP page)