Optimal Tour of Sweden

In May 2004, the traveling salesman problem of visiting all 24,978 cities in Sweden was solved: a tour of length 855,597 TSPLIB units (approximately 72,500 kilometers) was found and it was proven that no shorter tour exists. At the time of the computation, this was the largest solved TSP instance, surpassing the previous record of 15,112 cities through Germany set in April 2001. The current record an 85,900-city tour that arose in a chip-design application. The 24,978 cities Pictures of the Sweden Tour How was the tour found? Details of the computation Data sets for Sweden TSP and tour

Research Team

• David Applegate, Google Research
• Robert Bixby, Gurobi and Rice University
• Vašek Chvátal, Concordia University
• William Cook, University of Waterloo
• Keld Helsgaun, Roskilde University

• Office of Naval Research Grant N00014-03-1-0040, "Experimental Modules for Combinatorial Optimization and Mixed-Integer Programming"
• National Science Foundation, Grant DMI-0245609, "Local Cuts in Discrete Optimization and Mixed-Integer Programming"