.... Solving TSPs

World TSP

National TSPs


CIA Factbook

GEOnet Server



TSP Links


Home page

World TSP

We now have Pictures of the World TSP Tour.

World Tour
To provide a large-scale traveling salesman problem challenge, we put together data from the National Imagery and Mapping Agency database of geographic feature names and data from the Geographic Names Information System (GNIS), to create a 1,904,711-city instance of locations throughout the world. From the data bases, we selected all locations that were registered as populated places, and also included several research bases in Antarctica.

Each of the cities is specified by its latitude and longitude, given in decimal form (rather than minutes and seconds). The cost of travel between cities is specified by an approximation to the great circle distance on the Earth (treating the Earth as a ball). This cost function is a variation of the TSPLIB GEO-norm, adjusted to handle decimal degrees and scaled to provide the distance in meters rather than in kilometers. We call this cost function the GEOM-norm; a fragment of C-code to compute the travel costs can be found here.

The best reported tour for the World TSP has length 7,515,770,584, found by Xavier Clarist on June 22, 2020. Clarist's tour breaks the earlier record of 7,515,772,107 found by Keld Helsgaun on March 13, 2018, using a variant of his LKH heuristic algorithm. Previous records by Helsgaun were 7,515,772,212 (May 24, 2013), 7,515,778,188 (October 25, 2011), 7,515,786,987 (April 4, 2011), 7,515,796,609 (May 4, 2010), 7,515,877,991 (May 12, 2009), 7,515,947,511 (November 27, 2008), and 7,517,285,610 (September 16, 2003). An earlier record tour of length 7,518,425,642 was found by Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi Yasunaga (June 2, 2003), using a combination of iterated Lin-Kernighan and a parallel hybrid genetic algorithm.

The current best lower bound on the length of a tour for the World TSP is 7,512,218,268. This bound was established by the Concorde TSP code (June 5, 2007), using CPLEX as a linear-programming solver. The bound shows that Keld Helsgaun's tour has length at most 0.0474% greater than the length of an optimal tour.

We will be most happy to report any improved tour or improved lower bound that you may find.

Data  (Gzipped TSPLIB Format, world.tsp.gz, 11.5 mbytes)
World TSP

Back to TSP home.

Last Updated:  June 22, 2020
Contact:  bico@uwaterloo.ca