And One for the Road, Carl Zimmer

Discover, January 31, 1993

Among mathematics’ more complex puzzles is one known as the traveling salesman problem. Imagine you’re an Avon lady about to visit a group of cities. Your cheapskate boss won’t pay for the gas, so you want to map the shortest possible route that hits all your destinations and brings you back to your starting point.

Using brute force on the traveling salesman problem gets you nowhere. Even a short, five-city tour offers five choices for a starting point, four choices for the second destination, three for the third, and so on. Considering all the possible combinations of cities (which you get by multiplying 5 x 4 x 3 x 2 x 1) leaves you with 120 routes to check. A little tedious, but doable.

Raise the number of cities to 50, and the number of routes goes stratospheric: you now have more than 10^(64) possibilities. To check every route would take a supercomputer 10^(46) years.

A series of algorithms helped hone in on a solution in 1992. A team of researchers organized by William Cook of Bellcore in Morristown, New Jersey, won a race among several teams of researchers trying to find the shortest route connecting 3,038 possible cities. (The previous record was 2,392; 3,038 was chosen because it was the next largest number of points on a circuit board in a listing of traveling-salesman puzzles.) Cook programmed more than 30 Bellcore computers to solve the problem when their owners weren’t using them.

Cook’s team began by drawing 100 different routes. Each began at a randomly chosen city and traveled to the nearest neighbor, then the nearest neighbor to that city, and so on. After the routes were created, they tried to improve each one: to do so, they’d break the links between several cities and rearrange the path. They reconfigured each route 100,000 times and saved the shortest.

Still they didn’t know if it was the best of all possible routes; countless untried versions hadn’t even been considered. To claim to have solved the problem, they had to prove that a shorter route couldn’t exist. So they started chipping away from the other end, establishing a lower limit to the shortest possible route. One of the several approaches they used was to draw circles around the cities such that each circle touched its neighbor. At minimum, every route has to enter each circle at least once, reach its center, and leave it–in other words, travel the diameter (two radii) of the circle. Therefore, no route that reaches all destinations can be shorter than the sum of the diameters of all the circles. By devising such rules, the researchers boosted the minimum possible route higher and higher until the highest minimum matched the lowest they’d found by the first method.

In the real world, the traveling salesman problem can speed up the production of circuit boards used in computers. Boards have to be drilled to make connections at thousands or millions of points, and the more time the drill spends in motion, the more money is wasted. This year’s breakthrough, however, isn’t very pertinent to this problem. The time spent on the 30-plus computers would add up to a year and a half on a single machine. Engineers prefer fast approximations such as one created recently by David Johnson of AT&T Bell Labs and his colleagues. They can find a route within 2 percent of perfection for a million cities in less than three hours. It’s shaving off the last couple percentage points that’s so hard.

Still, for those who demand that science have a practical purpose, Cook’s story has a happy ending. His team came up with algorithms that can help arrange any kind of network–including a telecommunications grid such as Bellcore’s. “My managers are quite happy,” Cook says. “The amount of money we’ve saved has certainly paid for my salary for the past four years.”