The Ultimate Road Trip According to Science
Olson has computed the optimal route for a road trip around the continental US based on an algorithm he developed for most efficiently finding Waldo in the Where’s Waldo books. He was challenged to do so by Discovery News contributor Tracy Staedter.
The conditions for the trip were as follows:
- The trip must make at least one stop in all 48 states in the contiguous U.S.
- The trip would only make stops at National Natural Landmarks, National Historic Sites, National Parks, or National Monuments.
- The trip must be taken by car and never leave the U.S.
Now, as Tracy had compiled the list in the link above for the 50 landmarks to see, on in each state, the process of figuring out the map involved more than plotting them in a google maps route. All of the points had to be referenced for distance to each other to calculate the shortest distance you could drive and still hit all of the points. To calculate this, Olson used some computer wizardry against the Google Maps API to determine the shortest route between each point. Once this was finished, it became a classic Traveling Salesman problem: the landmarks needed to be ordered so that the entire trip was a short as possible, which meant finding routes that didn’t backtrack- a challenge in certain parts of the US.
The problem with Traveling Salesman problems is that they require an intense amount of computational resources to solve. As Olson put it, “If you started computing this problem on your home computer right now, you’d find the optimal route in about 9.64 x 1052 years — long after the Sun has entered its red giant phase and devoured the Earth.” He instead used a genetic-algorithm-based solution that basically starts with a solution that’s probably close to the best result and refines the nuances until the route is optimized from that starting point.
What Olson came up with is pretty cool. The trip would take 224 hours of straight driving- about ten days, but he estimates that it would take a person 2-3 months to complete.
The full map is available here. For the Google Maps links, and a special bonus version of the project based on major US cities, read Randy Olson’s original blog post. He has since done the same thing for Europe, and a walking tour of New York and Philadelphia, and also writes about a whole bunch of other really cool things.
I seriously love people who are this nerdy.