Squeezing the most fun possible into your vacation days is a challenge for anyone. If you’re a computer science researcher, however, it’s a challenge that comes with an answer.
Randy Olson is a postdoctoral researcher at the University of Pennsylvania, whose work involves biologically-inspired artificial intelligence. Recently he decided to merge his love of travel and algorithms by creating formula to plan the most efficient U.S. road trip ever.
Olson started off by laying a few ground rules, such as the fact that his journey should enable him to drive to the capitol buildings in the maximum number of U.S. states possible — excluding Alaska and Hawaii because they would take too long to reach, or in the case of Hawaii, be impossible without a plane. He also wanted to avoid routes that would require him to travel through foreign countries, since entering and leaving these places required a passport and wasted time crossing borders.
As Olson tells Digital Trends, this is essentially a variation on the classic “traveling salesman problem,” referring to a routing conundrum that is among the most-studied challenges in optimization. “The traveling salesman problem is difficult to brute force because there are millions of ways to order your trip to the cities, yet there’s typically only one ‘best’ route,” he says, describing it as finding “a needle in a computerized haystack.” Fortunately, computers can help.
“If you’ve ever used Google Maps to get the directions between two addresses, that’s basically what we have to do here,” Olson writes on his blog. “Except this time, we need to look up 2,256 directions to get the ‘true’ distance between all 48 state capitols.” One Google Maps API, Python script, and clever routing algorithm later, and Olson had his journey meticulously planned — which you can check out here.
Whether he’s been able to actually go on it yet is another question, unfortunately. “I wish I could hop in a car and go on the trip right now,” he tells us. “Alas, work keeps me too busy to take months-long trips like this one. My trips are typically limited to weekend road trips lately, which is why I like that this ‘limited budget’ algorithm [can suggest] shorter trips as well.”
In the meantime, he’s been thinking of more things to optimize — including gas stops, walking tours around the cities he plans to visit, and even adding time constraints so he can visit timely activities along the way.
“There’s a ton of room for optimization when it comes to road trips,” Olson says. Now if only he could bring himself to actually take a vacation day or two.
