Travelling Salesman Problem
The travelling salesman problem (TSP) is one of the most popular (and most studied) problems in computer science and operations research.
The (original) problem can be formulated as follows:
"If there are n cities a salesman must visit, and the distance between each pair of these cities is given, find the shortest tour where each city is visited exactly once and returning to your starting point."
The first thing you'll think is: "Can not be difficult..." That's true. You can easily solve the problem by comparing all possible solutions. However, when you have more than (let's say) 25 cities, it will be soon practically impossible to calculate all the ordered combinations (permutations). This is because the number of combinations is (n-1)!/2. (factorial of n = n * (n-1) * (n-2) * .. * 2 * 1) We have (n-1) choices for our second city, we have (n-2) for our third city, etc. Multiplying these together gives (n-1)!. Since our travel costs don't depend on the direction of our tour we should divide it by 2. That gives (n-1)!/2..
A nice example from Wikipedia/TSP
What you see here is an optimal tour throught the 15 largest cities of Germany. It is the best solution among 43,589,145,600 possible solutions. (14!/2)
That's a lot of possibilities eh?
I want to solve the TSP, which algorithms can I use?
As already said, you could use the all permutations-method. You can optimize this by using dynamic programming
, branch and bound
, linear programming
and combinations of these techniques. You'll need some good skills of mathematics and programming to efficiently use these techniques.
"In April 2006 an instance with 85,900 points was solved using Concorde TSP Solver
, taking over 136 CPU years." So an optimal TSP-tour of 85,900 "cities" is the record now. It's solved using megacomputers together with the best exact algorithm(s) available. So if you really want to calculate the most optimal tsp-tour for a large number of cities, it will take some serious time.
Ok, maybe an approximation of the optimal solution?..
Thank god there are approximation algorithms and heuristics. You can use these algorithms to quickly compute pretty good (sometimes optimal) solutions. Modern algorithms can find solutions for extremely large tours (millions of cities) withan a reasonable time. With a good probability just 2-3% away from the most optimal solution. For instance, you can use genetic algorithm
, ant colony optimization
, simulated annealing
, nice heuristics
and combinations of these. These algorithms are not very hard to understand.
Where can I get further information?
Of course there are lots of good websites containing useful information about the TSP. For example, the following links have some good extra information and theory about the TSP:
/ Official site
/ Some nice applets
/ Good documentation