Text Size

# Saturday Night Science: Simulated Annealing

The travelling salesman problem is one of the most-studied problems in combinatorial optimisation. It couldn’t be easier to state:

Given a list of cities and their locations (usually specified as Cartesianco-ordinates on a plane), what is the shortest itinerary which will visit every city exactly once and return to the point of origin?

Easy to ask, but devilishly difficult to answer…. The obvious way to solvethetravelling salesman problem would be to write down all of the possible sequences in which the cities could be visited, compute the distance of each path, and then choose the smallest. But the number of possible itineraries for visiting n cities grows as the factorial of n, which is written, appropriately as “n!”. The factorial of a positive integer is the product of that number and all smaller numbers down to one. Hence 2!=2, 3!=6, 6!=720, and 10!=3,628,800. As you can see, these numbers grow very rapidly, so as you increase the number of cities, the number of paths you have to compare blows up in a combinatorial explosion which makes finding the optimal path by brute force computation a hopeless undertaking.

“But”, you ask, “computers are getting faster every year. Why not just be patient and wait a few years?” Neither you, nor I, nor the universe has sufficient patience. The box at the top of this page contains thirty cities represented by red balls placed at random in the grey square, connected by a path drawn in blue lines in the order in which they were placed. Every time you press the “Place” button, thirty new randomly-placed cities are generated; you can change the number by setting the box to the right of the button. But let’s stick with thirty cities for the nonce.