World TSP
National TSPs
VLSI TSPs
CIA Factbook
GEOnet Server
GNIS Data
[
画像:Earth]
TSP Links
World TSP
[
画像: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,755,912, found by
Yuichi Nagata on October 17, 2025.
This tour improves by 44 meters the previous record of 7,515,755,956, found on February 15, 2021 by
Keld Helsgaun.
Yuichi Nagata's tour was found by adding the 7,515,755,956 tour to a population found by his GA-EAX heuristic and continuing the GA-EAX search.
The previous record tour of length
7,515,755,956 was found by Helsgaun on February 15, 2021 using his
LKH heuristic algorithm, starting with a tour of length
7,515,767,286, found by Xavier Clarist on February 11, 2021.
These two results together made a major improvment on earlier records, lowering the previous best known tour length by 14,628 meters.
To put it in perspective, note that from October 2011 through June 2020, the record was only improved by 7604 meters.
The three best tours are available as gzipped files in TSPLIB format:
7515755912.tour.gz,
world.7515755956.tour.gz and
world_7515767286.tour.gz.
Previous records were by Clarist 7,515,770,584 (June 22, 2020) and by Helsgaun 7,515,772,107 (March 13, 2018), 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 older 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.0471% 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: October 24, 2025
Contact: bico@uwaterloo.ca
