# The World TSP: a tour through 1,904,711 cities

The World TSP asks for the shortest round trip through 1,904,711 populated places on Earth. The best tour, found in October 2025, is known to be at most 0.0471% longer than an optimal one; the lower bound behind that guarantee has not moved since 2007.

## Problem

The instance lists 1,904,711 locations by latitude and longitude. The distance between two of them is an approximation of the great-circle distance on a spherical Earth, given in metres; the Waterloo pages call it the GEOM norm, a variant of the TSPLIB `GEO` norm adapted to decimal degrees, and publish a fragment of C code that computes it. Find a tour, a cyclic order visiting every location exactly once, of minimum total length, or prove that a given tour is optimal.

## Background

The instance was assembled on the Waterloo TSP pages as a large-scale challenge from two gazetteers: the National Imagery and Mapping Agency database of geographic feature names and the Geographic Names Information System. It contains every location registered as a populated place, plus several research bases in Antarctica. The National TSP instances are taken from the same data. Lower bounds come from Concorde, the linear-programming-based solver described by Applegate, Bixby, Chvátal and Cook (2006); the record tours come from heuristics, chiefly Helsgaun's LKH and Nagata's genetic algorithm with edge assembly crossover (GA-EAX).

## What is known

- Best tour: 7,515,755,912, found by Yuichi Nagata on 17 October 2025 by adding the previous record to the population of his GA-EAX heuristic. It improved Keld Helsgaun's tour of 7,515,755,956 (15 February 2021) by 44 metres.
- Best lower bound: 7,512,218,268, established by Concorde on 5 June 2007 with CPLEX as the linear-programming solver. The bound shows that the record tour is at most 0.0471% longer than an optimal one.
- Progress has slowed: from October 2011 to June 2020 the record improved by only 7,604 metres, while two tours in February 2021 lowered it by 14,628 metres. Earlier records go back to a 2003 tour of 7,517,285,610.
- The page (last updated 24 October 2025) invites improved tours and improved lower bounds, and offers the three best tours for download.

## What would count as progress

- A tour in TSPLIB tour format shorter than 7,515,755,912. A script checks that it is a permutation of the 1,904,711 cities and recomputes its length with the published GEOM distance code in seconds.
- A lower bound above 7,512,218,268, backed by a checkable certificate (for example the cutting planes and branching that produce it, as in the certified solution of `pla85900`, Applegate et al., 2009). Proving any tour optimal is a separate and far harder kind of progress.

## References

1. D. L. Applegate, R. E. Bixby, V. Chvátal and W. J. Cook (2006). *The Traveling Salesman Problem: A Computational Study*. Princeton University Press. https://press.princeton.edu/books/hardcover/9780691129938/the-traveling-salesman-problem
2. Y. Nagata and S. Kobayashi (2013). A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. *INFORMS Journal on Computing* 25, 346–363. https://doi.org/10.1287/ijoc.1120.0506
3. K. Helsgaun (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. *European Journal of Operational Research* 126, 106–130. https://doi.org/10.1016/S0377-2217(99)00284-2
4. D. L. Applegate, R. E. Bixby, V. Chvátal, W. Cook, D. G. Espinoza, M. Goycoolea and K. Helsgaun (2009). Certification of an optimal TSP tour through 85,900 cities. *Operations Research Letters* 37, 11–15. https://doi.org/10.1016/j.orl.2008.09.006

## Source

Imported from [Waterloo TSP pages, World TSP](https://www.math.uwaterloo.ca/tsp/world/index.html), curated by William Cook. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.