by Tony Moore
Everyone remembers a traveling salesman coming to the front door, wearing a white shirt and tie, no jacket, wiping his brow with a worn white handkerchief. “Hot one today,” he’d say, and you’d ask him inside, offer him a glass of lemonade. Then he’d try to sell you a vacuum cleaner, a set of encyclopedias or maybe a Bible.
What? You don’t remember this at all? You’ve only seen this character inhabiting movies and TV shows made before you were even born? Understood. But the plight of the traveling salesman is alive and well, and he might even be able to help you get through another “hot one.”
In mathematics, the traveling salesman problem (TSP) is a classical optimization problem that focuses on the following scenario: Given a list of cities and distances between them, what’s the shortest tour that visits each city exactly once and returns to the origin city?
That’s it. No biggie, right?
“The TSP is one of the most widely studied problems in combinatorial optimization, and while it's easy to state, it's one of the most challenging problems in operations research,” says Associate Professor of Mathematics Dick Forrester, noting that beyond obvious applications involving route planning, the TSP arises elsewhere, such as in circuit board fabrication, X-ray crystallography and genetic engineering.
But it’s summer, and people don’t think about X-ray crystallography as much as they think about going to theme parks and inevitably finding themselves standing in sweltering lines wishing they could game the system and move through these lines as fast as a roller coaster.
“One interesting application of the TSP is in trying to design a route through a theme park to see a selection of the attractions in the minimum amount of time,” says Forrester. He notes that this problem is significantly more difficult than the standard TSP, because while the distances between the attractions remain constant, the wait times of the rides vary throughout the day.
So Forrester and James Midkiff ’17 (mathematics, computer science) launched a student-faculty research project this summer, teaming up with two colleagues at Furman University, one of whom is Liz Bouzarth '03 (mathematics, physics), now an associate professor of mathematics at Furman. The Furman team had the Disney World data on wait times and distance between rides that they needed, and Forrester and Midkiff spent some time at Hersheypark, a short drive from Dickinson, collecting wait time information, travel distances and ride times. "James was the ideal student and research partner to work with on the project," Forrester says, "because of his strong background in computer programming and mathematical modeling.”
The project was funded by the Curley Endowment for Student-Faculty Research, something that Forrester calls "invaluable to the student-faculty research process at Dickinson, creating opportunities that just might not be there otherwise."
“Hersheypark and Disney World allowed us to map out two very different time-dependent traveling salesman problems (TDTSP),” says Midkiff, who explains that wait times at Disney World rides can vary unexpectedly as visitors move around the parks, while Hersheypark wait times are more stable, rising midday and settling lower in the morning and evening.
Forrester and Midkiff explored two types of algorithms for solving the TDTSP: metaheuristics and exact solution methods. Metaheuristics are procedures designed to find good solutions quickly, whereas exact solution methods set out to find the best possible solution. “The issue with exact methods is that they typically solve only smaller problems and may take a tremendous amount of time,” says Forrester.
The exact method developed by Forrester and Midkiff utilized an innovative model of the problem that was solved using commercial software. “While this technique guarantees the optimal solution, even after 10 hours it wasn’t able to find the best tour for Disney World,” Forrester continues. The method found success running Hersheypark data, however, and discovered the optimal tour of the 20 most popular attractions there.
On the other hand, in a display of the essential differences between the two approaches, the metaheuristic results were quick and effective, although less precise.
“With regards to metaheuristics, we focused our attention on developing what is known as a tabu search algorithm, while my colleague and his student at Furman University, working on a similar project, focused on genetic algorithms,” says Forrester. “Both of these metaheuristics were able to find near-optimal tours through the Magic Kingdom park in Disney World within a matter of minutes.”
The techniques Forrester and Midkiff developed for the project could easily be adapted to other scenarios involving the TDTSP, including routing a truck that takes not only the distance on the roads into consideration but also varying hourly and daily traffic patterns.
But for now, Midkiff is developing a website to navigate Hersheypark in the optimal way: Select the rides you want to hit and how many times you want to hit them, and then the algorithm will determine an optimal (or near-optimal) order to take them all on.
So there’s still hope for next summer, when it’s another hot one and you're headed to Hersheypark, wondering how you might manage to ride Skyrush four times before lunch and cool off on Riptide before Fahrenheit and Great Bear get your blood pumping again.
Published August 29, 2016