Burma and China: the two unsolved National TSP instances

The Waterloo TSP pages list traveling salesman instances built from the populated places of individual countries. Every one of them has been solved except two, Burma with 33,708 cities and China with 71,009, where the best tours lie within about 0.03% of proven lower bounds.

Problem

Given $n$ cities with coordinates, let the distance between cities $i$ and $j$ be their Euclidean distance rounded to the nearest whole number (the TSPLIB EUC_2D norm). Find a tour, a cyclic order visiting every city exactly once, of minimum total length. For the two instances below, either find a tour shorter than the best known or prove a lower bound equal to the best tour's length.

Background

The national instances were derived from the National Imagery and Mapping Agency database of geographic feature names, the same data behind the World TSP, and were put together to complement the TSPLIB collection. They range from 29 cities in Western Sahara to 71,009 in China. Lower bounds come from Concorde, the linear-programming-based TSP solver of Applegate, Bixby, Chvátal and Cook, which proves optimality by matching a tour with a cutting-plane bound and branching where needed (Applegate et al., 2006). The best tours on these pages come from heuristics such as Helsgaun's implementation of Lin–Kernighan (LKH) and Nagata's genetic algorithm with edge assembly crossover.

What is known

• According to the status table (last updated 31 July 2022), all other national instances are solved, among them Sweden (24,978 cities), Vietnam (22,775) and Italy (16,862).
• For bm33708 the best tour, 959,289, was found by Yuichi Nagata; Concorde's lower bound is 959,011, a gap of 278 units.
• For ch71009 the best tour, 4,566,506, also by Yuichi Nagata, sits 1,054 units above Concorde's bound of 4,565,452.
• The page invites improved tours and improved lower bounds.

What would count as progress

• A tour in TSPLIB tour format that is shorter than the listed best tour. A script verifies that it is a permutation of the cities and recomputes its rounded length in well under a second.
• A higher lower bound, or a proof of optimality that matches a tour, backed by a certificate that can be checked independently (as was done for the 85,900-city instance pla85900, Applegate et al., 2009). This is a separate and harder kind of progress than a better tour.

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. 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
3. 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
4. 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

Source

Imported from Waterloo TSP pages, status of the National TSP instances, 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.