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. This is currently the largest solved TSP instance, surpassing the previous record of 15,112 cities through Germany set in April 2001. 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, AT&T Labs - Research
• Robert Bixby, ILOG and Rice University
• Vašek Chvátal, Rutgers University
• William Cook, Georgia Tech
• 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"