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