THE TRAVELING SALESMAN PROBLEM (TSP)

The Traveling Salesman Problem is a classical problem that has discrete and combinatorial properties. The first example of it can be found as early as the 1800s and has been first studied by mathematicians during the 1930 in Vienna and at Harvard. (follow up)

So let's just define what it is: A salesman has to travel a number of cities and return to his starting point after the completion of the tour. Since money is time, he is interested in finding the shortest route that will allow him to visit all cities. With an increasing number of cities the number of possible combinations also increases (let's just assume that the cities are all interconnected. Let's look at an example. Say there are 3 cities. How many different routes are there?

The quick way to calculate this is the use of factorials (n!). The way to calculate a factorial is by multiplying it with itself minus 1 until 1 so (3!=3*2*1=6). If you think that numbers can’t be trusted go ahead and write all the combinations for 4 cities, but I can tell you that it will be 4! (=24). So with an increasing number of cities the number of possible paths also increases. For example with 10 cities there are 3.628.800 different routes. Well that’s still not too bad. (you might not want to write down all the combinations but figure if out with the help of your PC. The slick way to solve this problem is using an algorithm that doesn’t calculate the shortest route for each combination but that evolves to the shortest path.

Simulated annealing uses a process that is derived from the process of annealing (consecutive heating and cooling of a substance). Of the 3 it is the simplest. (follow up)