The Cellar - Dec 31st, 2016: Pub Crawl

Since you Dwellers would never drink, smoke or dance the hoochie koo, I'll explain. A pub crawl is a mobile party that moves from bar to bar until they can't. Now if you want to hit as many places as possible it's a good idea to figure out the most efficient route.

Enter the math nerds; William Cook, Combinatorics and Optimization, University of Waterloo, Canada; Daniel Espinoza, Gurobi Optimization, USA; Marcos Goycoolea, School of Business, Universidad Adolfo Ibanez, Chile; and Keld Helsgaun, Computer Science, Roskilde University, Denmark.

Quote:

The work was carried out over the past two years. We, of course, did not have in mind to bring everything mathematics has to bear in order to improve the lot of a wandering pub aficionado. Rather, we use the UK pubs problem as a means for developing and testing general-purpose optimization methods. The world has limited resources and the aim of the applied mathematics fields of mathematical optimization and operations research is to create tools to help us to use these resources as efficiently as possible.

https://cellar.org/2016/pubcrawl.jpg
You can see the big (50 inch) version at the link below.

They worked out the most efficient pub crawl in the United Kingdom, connecting 24,727 pubs in the shortest possible closed loop, 45,495,239 meters, or about 28,269 miles. Because it’s a loop, you can jump on at any point and it will bring you back there.

Quote:

Our pubs computation used a beefed-up version of the Concorde implementation of the TSP cutting-plane method. Even if you are in a hurry, you might want to see for yourself how the process solves smaller examples on an iPhone or iPad by downloading the free Concorde App.

In working with road data, we were faced with the additional challenge of finding the correct TSP solution even though we could not possibly ask Google for all 305,699,901 pub-to-pub distances. To handle this, we ran the cutting-plane method in tandem with a beefy variant of Keld Helsgaun's LKH code.

LKH combines a powerful local-search technique with a genetic algorithm to produce a high-quality tour, say of length U. Along the way, LKH discovers pairs of pubs that look promising to include in any short tour, so for these pairs we ask Google for the correct walking distances.

At the link they explain in much detail I won't bore you with, because I know you want to get crawlin'. :drunk: