Optimal 85,900-Point 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. The 85,900-city VLSI application Pictures of the solution The 15-year race for shorter tours Solving the problem Data sets for the pla85900 TSP and tour

Research Team

• David Applegate, Google Research
• Robert Bixby, Gurobi and Rice University
• Vašek Chvátal, Concordia University
• William Cook, University of Waterloo
• Daniel Espinoza, Google
• Marcos Goycoolea, Universidad Adolfo Ibanez
• Keld Helsgaun, Roskilde University

• Office of Naval Research Grant N00014-03-1-0040, "Experimental Modules for Combinatorial Optimization and Mixed-Integer Programming"
• National Science Foundation, Grant DMI-0245609, "Local Cuts in Discrete Optimization and Mixed-Integer Programming"
• National Science Foundation, Grant CMMI-0726370, "An Exact Rational Solver for Mixed Integer Programming"

• H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech