Algorithmics - The Computing Universe: A Journey through a Revolution - page 96

Since the pioneering work of these RAND researchers, the challenge of the
traveling salesman has continued to attract the attention of researchers. The
record for finding the optimal tour has been steadily increased from 48 cities
( Fig. 5.14 ) in 1954; to 64 by Michael Held and Richard Karp in 1971; to 532, then
1,002, and then 2,392 cities by teams led by Martin Grotschel and Manfred
Padberg in 1987; to tours of 13,509 cities in the United States in 1998 and of
24,978 cities in Sweden in 2004 by Concorde, the current champion TSP pro-
gram. The Concorde program was developed by David Applegate, Robert Bixby,
Vasek Chvatal, and William Cook and is available over the Internet. In 2006,
they used their program to find the shortest travel time for a laser to cut con-
nections in a Bell Labs computer chip. The result was an optimal tour for an
85,900 “city” problem ( Fig. 5.15 ). This stands as the record TSP for which the
optimal tour is known. Larger problems, such as the 100,000-city Mona Lisa
problem created by the artist Bob Bosch and shown in Figure 5.16 , are signifi-
cantly more difficult than the computer chip problem, which has many “cities”
close together on straight lines. Currently the best solution for a Mona Lisa tour
is still 0.0026 percent above the bound for the optimal tour!
Before we leave the traveling salesman problem we should say that although
finding a provably optimal tour is still computationally challenging, there are
many practical ways to find very good approximate solutions to the TSP. Most
modern algorithms are variants on a method devised by Bell Labs researchers
Shen Lin and Brian Kernighan in 1973. This systematizes the process of mak-
ing incremental tour improvements on some initial tour. A “2-opt” move is an
improvement wherein two edges are deleted and the tour reconnected with two
shorter edges. Similarly, we can look for 3-opt moves and more. Danish com-
puter scientist Keld Helsgaun improved on the original Lin-Kernighan method
in 1998 by explicitly incorporating a search for 5-opt exchanges, reconnect-
ing ten edges at a time. Combining Lin-Kernighan with ideas from simulated
annealing in physics, in 1991 researchers Olivier Martin, Steve Otto, and Ed
Felten at Caltech developed what is now known as the Chained Lin-Kernighan
algorithm. In 2000, this method was used on a 25,000,000-city problem to find
a tour that was only about 0.3 percent greater than the theoretical shortest
path. This is still the dominant algorithm for use with very large data sets. The
TSP is an important optimization problem for many types of problems - from
various pickups and deliveries, to finding markers on genomes, to moving tele-
scopes and manufacturing electronic circuit boards.

Fig. 5.14. Optimal tour around the
United States visiting forty-eight state
capitals. Researchers George Dantzig,
Ray Fulkerson, and Selmer Johnson from
the RAND Corporation did not actually
use the forty-eight state capitals in their
classic 1954 solution of the forty-eight-
city problem.

Complexity theory

As Charles Babbage foresaw in the quotation that introduces this chapter,
now that we have computers, the question of how to find the fastest algorithm
to solve a particular problem moves to center stage. In our discussion on sorting

Fig. 5.15. Section of the optimal tour for
the 85,900-“city” problem.