Salesman's world tour

From: London Financial Times, June 11, 1998

A traveling salesmen has to visit a specified number of cities. What is his shortest route?

This famous conundrum is typical of a class of mathematical problems that come up repeatedly in sentence, engineering and management. Examples range from drilling holes in printed circuit boards to routing helicopters around oil rigs.

The point is that the problem becomes increasingly difficult to solve as the number of cities increases, along with the number of possible routes. Computers find it particularly hard. If a computer had to calculate the lengths of all possible routes between 100 cities and find the shortest route it would take billions of years for it to complete the calculation.

But researchers at Rice University in the US are finding new ways to tackle the problem using mathematical models and high performance computing. They have recently found a solution to the traveling salesman problem for 13,509 cities - a big advance on their previous record of 7,397 cities. which was set in 1994.