A shortest-possible walking tour through the pubs of the United Kingdom — that’s an advanced form of the mathematicians’ favorite, The Traveling Salesman Problem. William Cook and colleagues at the University of Waterloo tackled this nastily complex problem:
Nearly everyone in the UK knows by heart the best path to take them over to their favorite public house. But what about jotting down the shortest route to visit every pub in the country and return home safely? That is what we set out to do….
Using geographic coordinates of 24,727 pubs provided by Pubs Galore and measuring the distance between any two pubs as the length of the route produced by Google Maps, what is the shortest possible tour that visits all 24,727 and returns to the starting point? …
This is the problem we have solved. The optimal tour has length 45,495,239 meters. To be clear, our main result is that there simply does not exist any pub tour that is even one meter shorter (measuring the length using the distances we obtained from Google) than the one produced by our computation. It is the solution to a 24,727-city traveling salesman problem (TSP).
The UK Pubs tour is easily the largest such road-distance TSP that has been solved to date, having over 100 times more stops than any road-distance example solved previously by other research groups.
Here’s one low-resolution sliver of what is a much more detailed map of the tour:
(Thanks to Mason Porter for bringing this to our attention.)
BONUS: William Cook’s book on the history of the Traveling Salesman Problem.