You might call it the ultimate road trip. Professor William Cook, of the University of Waterloo, led an international team that has found the shortest-possible route to visit 49,603 of the sites listed on the National Register of Historic Places in the U.S.
An expert in the Travelling Salesman Problem (TSP), Cook, a professor in Waterloo’s Faculty of Mathematics, says the best route to go to all and return home is 350,202 kilometres long. The National Register of Historic Places lists more than 90,000 sites. Cook selected 50,000 of them. The program removed duplicates, such as landmarks or bridges shared between different states.
“Our goal was not to plot life-defining vacations for history buffs,” said Cook. “Rather, we use the travel problems as a means for developing and testing optimization methods, which can help find the most efficient routes for delivery trucks that bring packages to your door, to schedule production runs in factories and various other applications in industry, science and commerce.”
The project ran on 300 computers since March, which translates to 178 computing years to solve it. It includes 250 times more stops than any road-distance example solved previously by other research groups and builds on the team’s recent calculation of the shortest route to nearly 25,000 pubs in the U.K.
