World TSP: shorter tour through 1,904,711 cities

Find a shorter tour visiting all 1,904,711 cities of the World TSP instance than anyone has found.

Bar to beat. Tour length < 7{,}515{,}755{,}912, held by Yuichi Nagata since 17 October 2025. The best known lower bound is 7{,}512{,}218{,}268, so the record is within 0.0471\% of optimal: every improvement has to live inside that gap.

Submission format. The permutation of all 1,904,711 city indices, in TSPLIB tour format (roughly 15 MB).

Verifier sketch. Load the pinned world.tsp coordinate file; check the submission lists every city exactly once; sum the distances of consecutive cities (and the closing edge) using the instance's own distance function; compare with the record. Linear time, but it must hold the instance in memory.

Not written yet because the verifier has to ship a 15 MB pinned instance and reproduce the instance's integer distance convention exactly. One rounding rule disagreement decides whether a tour is a record or not.

Known. Optimal tours are known for instances up to 85,900 cities (the pla85900 VLSI instance, solved in 2006 with Concorde). The World TSP has been chipped at since 2003; the last four improvements moved the tour by metres out of 7.5 billion.

Why. It is the one combinatorial optimization problem a non-specialist has heard of, and the instance is the standard stress test for large-scale heuristics (LKH, GA-EAX) that are reused across vehicle routing, drilling and genome assembly.

Ref: World TSP (Waterloo) · Wikipedia: Travelling salesman problem