the traveling salesman problem challenge for cheeseheads

Bucky the Badger is ready to tour Wisconsin!

This TSP blog post is in honor of Bill Cook’s lecture at the University of Wisconsin on Monday, April 7:

HF Deluca Forum

The Discovery Building.

12 – 1 pm.

More info: go.wisc.edu/salesman.

We are very excited to host Bill on Monday. Bill informally launched an information Dairyland TSP challenge on twitter, a tour through all 165 stops in America’s Dairyland [link to pdf]. What is the shortest tour? Hint: try using Bill’s TSP iPhone/iPad app!

@lauramclay Cheese TSP Challenge? 165 stops in America's Dairyland. http://t.co/iInDakb6I9 pic.twitter.com/A8G92eZqEs

— Bill Cook (@wjcook) April 4, 2014

For more reading:

• Bill has some fantastic TSP resources on his web site.
• My colleague Jordan Ellenberg’s reviewed In Pursuit of the Traveling Salesman in the Wall Street Journal.
• Here is my review of In Pursuit of the Traveling Salesman.
• How to visit all 30 Major League Baseball stadiums in the shortest amount of time.
• A Christmas brain teaser (yes, it involves the TSP)

Here are a few other TSP links.

xkcd on the TSP

A TSP genetic algorithm that finds a tour of the lower 48 state capitals. Courtesy of MathGifs

This video shows a visualization of Greedy, Local Search, and Simulated Annealing strategies for solving the Traveling Salesman problem.