One of my blog posts about starting a fire at a gas station was featured on the math podcast The Other Half called “The Road Trip” by podcasters and professors Dr. Annie Rorem and Dr. Anna Haensch [Listen here] The podcast is about taking an optimal road trip (the Traveling Salesman Problem (TSP)) and rare risks associated with travel.
In The Road Trip, Anna and Annie look into the math that undergirds the great American summertime tradition of rolling down the windows, turning up the stereo, and touring the countryside by automobile.
Randy Olson has made the planning part easy by computing the optimal road trip across the U.S. His work to minimize the miles between landmarks in the lower 48 has been featured in the Washington Post and on Discovery News. In fact, Tracy Staedter of Discovery News can be credited not only with encouraging Olson to tackle this problem, but also with determining the list of landmarks he used. If you have a road trip you’d like to optimize, check out his code here.
And, because cars don’t run on math alone, we also consider the necessity of refueling on the road. In particular, we ask Laura McLay to weigh in on gas station safety, as she computes the conditional probability of blowing yourself up while you’re pumping gas.
“The Road Trip” is n excellent podcast! Thanks to Annie and Anna for doing such a great job and for being math ambassadors. I look forward to future episodes.
The Other Half is part of ACME Science, which offers several other math and science podcasts.
One thing I would like to add to the podcast is that there are real applications of the TSP and risk analysis. We academics don’t always sit up in our ivory towers coming up with silly problems to solve that are divorced from the real world. We need to be able to characterize rare risks for numerous applications (e.g., nuclear power risks) and then communicate those risks to others for managing rare but potentially catastrophic risks. I have a few links to related blog posts at the bottom of this post. Likewise, the TSP isn’t just used to plan summer road trips. It’s used by trucking and delivery companies to plan routes, in gene sequencing, for meals-on-wheels deliveries, and in emergency response after a disaster.
A second point is that we really can optimally solve many instances of the TSP, and certainly the ones used for planning road trips. We do not always have to settle for a solution that is “good enough.” It’s true that there are more feasible solutions to many problems than there are stars in the galaxy, but we don’t solve the problems by brute force. We more intelligently solve the problems using optimization algorithms such as the simplex algorithm (a linear programming algorithm) and cutting planes (an integer programming method). Optimization algorithms traverse through the search space and find the single optimal solution among trillions of possibilities sometimes in mere seconds or minutes. It’s truly astonishing and a great contribution to basic science.
If you want more, Bill Cook is the world’s expert on the TSP and he has many examples of optimal solutions on his web site, including a TSP rout of 24,978 cities. Read Bill Cook’s (@wjcook) book and blog about the TSP for more details about the TSP’s history, algorithms, and people.
Related posts:
- what is the (conditional) probability of exploding when filling your car up with gas?
- Type II errors are the ones that get you fired: the Atlanta edition
- operations research, disasters, and science communication
- what is the optimal false alarm rate for tornado warnings?
- the traveling salesman problem challenge for cheeseheads
- Bill Cook’s TSP talk at the University of Wisconsin-Madison
- Your ideal summer beach read: In Pursuit to the Traveling Salesman problem
Punk Rock Operations Research 
July 23rd, 2015 at 3:05 pm
And – if you like that sort of thing – there is a fun puzzle game based on a prize-collecting, subset selection TSP, called Rogo. You can find it on the AppStore. Or Google Rogo Puzzle to find out more.