YouTube, mov, or mp4
The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.
Hey Siri, how can I solve the TSP?
YouTube, mov, or mp4
|
| Optimal road trip to visit all 647 colleges on Forbes' list. |
|
|
|
|
| |
|
|
|
$7.98 at Labyrinth Books Chapter 1 as pdf file Facebook Page |
|
iTunes Preview App Support Page NY Times Article |
| Pokemon Go Tours |
|
Shortest routes to Catch 'em All | |
| Tour for Extra Milers |
|
Drive to all 3100 US county seats | |
| Queen of College Tours |
|
Optimal road trip to visit 647 colleges | |
| Hiking Tour of Austria |
|
Get a view of 100 mountain peaks | |
| 50 USA Landmarks |
|
Dicussion of wildly popular USA tour | |
| TSP Tutorial in Python |
|
Nice intro to the TSP by Peter Norvig | |
| Romanian TSP |
|
TSP image by Cerasela Crisan and Camelia Pintea. | |
| United States TSP |
|
$500 Prize for best tour through 115,475 US cities. | |
| Scientific American |
|
Short piece on Yogi Berra and the TSP | |
| Travelling Salesman |
|
Thriller movie centered around a solution of the TSP | |
| Mona Lisa TSP |
|
$1,000 Prize for a 100,000-city challenge problem. | |
| pla85900 |
|
Solution of a 85,900-city TSP. | |
| Iowa Tour |
|
Optimal route for a 99-county campaign tour. |
|
|
The Traveling Salesman Problem: A Computational Study by Applegate, Bixby, Chvatal, and Cook.
|
|
Description of the techniques we use to compute lower bounds on the lengths of all TSP tours.
|
|
Optimal solution for visiting all 24,978 cities in Sweden. Tour has length approximately 72,500 kilometers.
|
|
The TSP was featured in a contest run by Proctor and Gamble in 1962. The challenge problem had 33 cities.
|
|
A graphical user interface available for Concorde on Windows' platforms.
|
|
The Concorde TSP solver is used in a genome sequencing package from the National Institutes of Health.
|
|
A collection of 25 TSP challenge problems consisting of cities in Argentina through Zimbabwe.
|
|
Pages describing some of the history of the TSP as a mathematical and computational challenge.
|
|
A flash game to find the optimal tour through a randomly generated set of city locations.
|
|
A challenge problem consisting of the locations of 1,904,711 cities throughout the world.
|
| |
|
|
The work described here is supported by the Office of Naval Research (N00014-09-1-0048) grant. A good source for computational research on the traveling salesman problem and general optimization is the journal Mathematical Programming Computation. See the pages Research in the Faculty of Mathematics for an overview of work at the University of Waterloo.
Contact: William Cook (bico@uwaterloo.ca)