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.
|