The traveling salesman problem, or TSP for short, is this: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point.  In these pages we report on our ongoing project to solve large-scale instances of the TSP.

TSP Cutting-Plane Applet, Interactive tool for studying the cutting-plane method for the traveling salesman problem.

Solution of a 15,112-city TSP         History of the TSP         TSP Picture Gallery         Applications         World TSP Challenge and National TSPs         VLSI TSP Test Instances           Concorde Computer Code   (Benchmarks)         QSopt LP Solver         The Cutting-Plane Method         Unsolved Problems in the TSPLIB         Research Papers         Talk by Vašek Chvátal         Talk by William Cook            Links to the TSP Home Page

Traveling Salesman Problem Links

• TSPLIB - Gerd Reinelt's library of TSP instances.
• TSPBIB - Pablo Moscato's listing of TSP references.
• 8th DIMACS Implementation Challenge - Testing of TSP heuristics.
• LKH - Keld Helsgaun's variant of the Lin-Kernighan heuristic.
• Jesper Larsen's Papers on the TSP.
• A Farmer's Daughter in Our Midst - An inteview with Vašek Chvátal.

Research supported by the following grants.

• Office of Naval Research Grant N00014-01-1-0058
• Rice-Compaq Research Initiative

David Applegate, Robert Bixby, Vašek Chvátal, William Cook
Back to TSP home.