The 30 unsolved VLSI traveling salesman instances

The VLSI collection on the Waterloo TSP pages holds 102 traveling salesman instances taken from chip-design data, with 131 to 744,710 cities. Seventy-two are solved; thirty are not, and for twenty-four of those the status table lists no lower bound at all.

Problem

Each instance is a set of points in the plane; the distance between two points is their Euclidean distance rounded to the nearest whole number (the TSPLIB EUC_2D norm). Find a shortest tour that visits every point exactly once and returns to the start. For each open instance, either find a tour shorter than the best known or prove a matching lower bound.

Instances with a proven lower bound:

Instances with no lower bound listed, and their best tours: fma21553 66,527; lsb22777 60,977; xrh24104 69,294; bbz25234 69,335; irx28268 72,607; fyg28534 78,562; icx28698 78,087; boa28924 79,622; ird29514 80,353; pbh30440 88,313; xib32892 96,757; fry33203 97,240; bby34656 99,159; pba38478 108,318; ics39603 106,819; rbz43748 125,183; fht47608 125,104; fna52057 147,789; bna56769 158,078; dan59296 165,371; sra104815 251,342; ara238025 578,761; lra498378 2,168,039; lrb744710 1,611,232.

Background

The collection was provided by Andre Rohe and is based on VLSI data studied at the Research Institute for Discrete Mathematics (Forschungsinstitut für Diskrete Mathematik) of the University of Bonn. All lower bounds on the pages come from Concorde (Applegate et al., 2006). Every instance up to 13,584 cities is solved, including xvb13584.

What is known

• The status table was last updated on 3 May 2017. Its best tours come from Keld Helsgaun; Hung Dinh Nguyen; Changxing Dong, Gerold Jaeger, Paul Molitor and Dirk Richter; Kazuma Honda, Yuichi Nagata and Isao Ono; Yuichi Nagata; and Xavier Clarist, who holds the records for the five largest instances.
• For the six instances in the first table, the gap between tour and bound is between 7 and 16 units.
• 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. A script checks that it is a permutation of the points and recomputes its rounded length in seconds, even for the largest instance.
• A first lower bound for one of the twenty-four instances without one, or a proof of optimality for any open instance, backed by a certificate that can be checked independently (as for pla85900, Applegate et al., 2009). This is a separate and harder kind of progress than a shorter 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. 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. 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

Source

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