Traveling Salesman Problem

The Traveling Salesman Problem, or TSP for short, 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.

Optimal Tours
Screen shot of TSP DIY app front page
Introduction to the TSP
Math Encounters, August 4, 2021
National Musuem of Mathematics
Traveling Salesman Problem DIY
Web app for learning/teaching TSP solution methods.

Screen shots of Concord TSP app
TSP app for iPhone/iPad/Mac
Concorde available on the Apple App Store. It's free!

Amazon Route
Path in Gaia DR2 tour
Winning $100,000 in the Amazon Last Mile Routing Research Challenge. How to visit 1.33 billion stars.

TSP Postcards
Connecting the Dots in the TSP
TSP: Postcards from the edge of Impossiblity
IFORS Distinguished Lecture
EURO 2019, Dublin
Connecting the Dots in the TSP
MAA Invited Address
2018 Joint Math Meetings

Screen shot of UK Pubs tour
Screen shot of US50K points
Optimal crawl to 49,687 pubs in the UK. Visit 49,603 historic sites in the US.

Screen shot of NL tour
Cycling tour to 57,912 Dutch monuments.



TSP Tutorial in Python
Nice intro to the TSP by Peter Norvig
Cutting-plane method YouTube video (in Siri's voice)
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
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.

In Pursuit of the Traveling Salesman: Mathematics and the Limits of Computation, available for $7.98 @ Labyrinth Books. The Traveling Salesman Problem: A Computational Study by Applegate, Bixby, Chvatal, and Cook.

The work described here is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Department of Combinatorics and Optimization at the University of Waterloo.

Contact: William Cook (bico@uwaterloo.ca)