Solution of a 15,112-city TSP

On April 20th, 2001, David Applegate, Robert Bixby, Vašek Chvátal, and William Cook announced the solution of a traveling salesman problem through 15,112 cities in Germany. This was the largest TSPLIB instance that had been solved at the time, exceeding the 13,509-city tour through the United States that was solved in 1998.

The optimal tour has length 1,573,084 in the units used in TSPLIB; this translates to a trip of about 66,000 kilometers through Germany.  Pictures of the optimal tour can be found at Optimal Tour .

The computation was carried out on a network of 110 processors located at Rice University and at Princeton University.  The total computer time used in the computation was 22.6 years, scaled to a Compaq EV6 Alpha processor running at 500 MHz.  Details can be found in the Computation section.

In German Tours we display the 15,112-city tour together with other tours through Germany that have played a role in the history of the TSP.