Logo pla85900 Home
Concorde Plane
  Home
  Optimal Tours
pla85900 Home
  The Application
  Pictures
  15-Year Race
  Solution
  Data Sets

Optimal 85,900-Point Tour

Tiny Tour
The largest solved instance of the traveling salesman problem consists of a tour through 85,900 cities in a VLSI application that arose in Bell Laboratories in the late 1980s. The computation with Concorde was carried out in 2005/06 and reported in the book The Traveling Salesman Problem: A Computational Study. The instance is called pla85900 in Gerd Reinelt's TSPLIB; the shortest possible tour for the problem has length 142,382,641 units. With the solution of pla85900, the complete TSPLIB collection of challenge problems has now been successfully solved with the Concorde code.

Research Team

Support for this research was provided by the following grants
Computer facilities and support were provided by
Home | pla85900 Home Back
Last Updated: August 2022