TSP Records: From 49 Cities in 1954 to 85,900 in 2006

Proven optimal tours grew from 49 cities in 1954 to 85,900 in 2006 through optimization, not neural networks. The timeline and how to read claims.

Guide: AI BasicsLast verified: October 20265 min read

The largest traveling salesman problem solved to proven optimality grew from 49 cities in 1954 to 85,900 in 2006, a gain of about 1,750 times in 52 years. Every step on that list came from mathematical optimization on faster computers, not from a neural network. The Waterloo list still ends at 85,900 cities as of October 2026, so 2006 is the latest year on it. That makes the record a handy measuring stick for any claim that artificial intelligence "solves" the problem, because it separates finding a good tour from proving that no better one exists.

Key takeaways

  • In 1954 George Dantzig, Ray Fulkerson, and Selmer Johnson at the Rand Corporation proved a tour through 49 locations optimal, working by hand with linear programming.
  • The University of Waterloo's milestone list records 13 solved instances between 1954 and 2006, ending with 85,900 cities.
  • The 1954 problem alone has roughly 6.2 x 10^60 possible tours, so brute force was never an option.
  • The 85,900-city instance came from a chip-design application at Bell Laboratories in the late 1980s, and its optimal tour has length 142,382,641.
  • Proving optimality and finding a short tour are different tasks, and records usually refer to the first.

The 1954 problem: 49 points, a road atlas, and a pencil

At Rand, Dantzig, Fulkerson, and Johnson picked one location in each of the 48 U.S. states plus Washington, D.C., and took driving distances from a Rand McNally atlas. They found a tour and then proved that no shorter one exists, an argument built on linear programming. According to the University of Waterloo's history page, all of the computation was done by hand because electronic computers were scarce, and Newsweek reported on the work in its July 26, 1954 issue.

The method now goes by the name branch-and-cut. It builds a lower bound on the tour length from linear inequalities, adds new inequalities where the bound is loose, and splits the problem when needed. The Waterloo page calls the idea central to most commercial optimization software.

Thirteen solved instances, 1954 to 2006

YearCitiesResearchers
195449Dantzig, Fulkerson, Johnson
197164Held, Karp
197567Camerini, Fratta, Maffioli
1977120Grotschel
1980318Crowder, Padberg
1987532Padberg, Rinaldi
1987666Grotschel, Holland
19872,392Padberg, Rinaldi
19947,397Applegate, Bixby, Chvatal, Cook
199813,509Applegate, Bixby, Chvatal, Cook
200115,112Applegate, Bixby, Chvatal, Cook
200424,978Applegate, Bixby, Chvatal, Cook, Helsgaun
200685,900Applegate, Bixby, Chvatal, Cook, Espinoza, Goycoolea, Helsgaun

The table follows the milestones page maintained at the University of Waterloo, and the dates are the years that page gives.

What the growth does and does not show

From 1954 to 1980 the record rose from 49 to 318 cities, and from 1987 to 2006 it rose from 2,392 to 85,900. The sources consulted do not break the gain down by cause, but the successive records came from successive cutting-plane codes run on the computers of their day. The number of possible round trips through n cities is (n minus 1) factorial divided by 2, so each added city multiplies the count. For 49 cities that is about 6.2 x 10^60 (the arithmetic is illustrative, not from the source), and for 120 cities about 2.8 x 10^196. No computer can list them, which is why every solution on the table relied on bounds that discard almost all tours at once.

A record belongs to one named instance. A different 85,900-city map could be easier or harder, so the figure says nothing about every instance of that size.

The list has not moved since 2006. Waterloo's page shows no later entry and no note about an expected one, so no next milestone can be sourced here. Any future claim would need to match the table's standard: a named instance and a proof of optimality.

Where the 85,900-city instance came from

The record instance, pla85900, models a chip-design task from Bell Laboratories in the late 1980s. Its optimal tour, found with the Concorde solver in 2005 and 2006, has length 142,382,641 in the instance's units. The credited team includes David Applegate, Robert Bixby, Vasek Chvatal, William Cook, Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun. Concorde is written in ANSI C and is available for academic research use, with other uses requiring a license from William Cook.

Reading a "solved" claim in the AI era

  • Does the claim say the tour is proven optimal, or only that it is short?
  • Which instance, how many cities, and what distance rule (road, straight line, or rounded)?
  • Is the baseline a proven bound, or the best tour another program happened to find?
  • How much hardware time was used, and is it reported?
  • Does the method need a mathematical solver underneath it?

FAQ

Did artificial intelligence solve the 85,900-city instance?

No. The solver credited on the Waterloo page is Concorde, an optimization program, and the pages consulted mention no machine learning model.

Why was the 1954 result such a big deal?

It showed that a tour could be certified optimal without checking every route. The technique it introduced remains central to optimization software.

Is the record likely to grow?

The milestone page ends in 2006, and no later entry appears there as of October 2026. Whether a larger instance has been solved elsewhere is not established by that page.

Can a person use Concorde for a delivery business?

The Waterloo page states the code is available for academic research use and that other uses require contacting William Cook about licensing.

Last verified: October 2026

Sources

  • Milestones in the Solution of TSP Instances, University of Waterloo, 2026
  • The 49-city (USA 50) problem page, University of Waterloo, 2026
  • pla85900 solved instance page, University of Waterloo, 2026
  • Concorde TSP Solver page, University of Waterloo, 2026

New to artificial intelligence?

Start with the basics, then follow the guides to tools, rules, and effects on society.

Start with AI Basics