In this third of a trinity of posts involving the travelling salesman problem, we finally use the sophisticated algorithms at our disposal as they were intended: drinking with peak efficiency.

With the aid of a well-placed Christmas present detailing the best pubs in London, I found the optimal route around a reasonable subset of them.

In no particular order then, from George Dailey’s excellent book the 22 pubs in question are

• Ye Olde Cheshire Cheese
• The Prospect of Whitby
• The French House
• The Blackfriar
• The Grapes
• The Ship Tavern
• The Nags Head
• The Mayflower
• The Spaniards Inn,
• The Dove
• Cittie of York
• The George Inn
• The Lamb and Flag
• Hoop and Grapes
• The Flask
• The Grenadier
• The Anchor
• The Guinea
• The Cross Keys
• The Dog and Duck
• The Swan
• Ye Olde Mitre

Some of these are unfortunately spread quite far from the rest of the pubs, e.g. the Dove in Hammersmith (though in no way diminishing their charm). In the interest of efficient pub crawling, I therefore slimmed this list down to those pubs listed in bold, plotted below in red.

Now it’s pretty clear here what the best route should be, but let’s be extra sure. There may be, for example, quicker routes via public transport between pubs which look relatively far apart.

To accomplish this I need to build up a matrix which lists the travel time between pubs and (assumed symmetric). Once I’ve got this, I have the adjacency matrix of the complete graph over the set of the 8 selected pubs and I can compute the optimal travel route amongst them.

To get the travel times, I used the Google directions API. This is a very simple API to use, involving web requests like

r = requests.get('https://maps.googleapis.com/maps/api/directions/json?
origin=' + orig + '&destination=' + dest + '&mode=transit&key=' + key)
data = r.json()
steps = data['routes'][0]['legs'][0]['steps']

where orig, dest and key are the origin/destination postcodes and developer API key respectively. The response is a chunk of JSON which contains all of the route details, crucially including the travel time. The individual parts of the journey are tabulated in the steps list.

After a few hundred API calls (thanks Google!) I have the matrix:

The problem of finding the quickest route through these pubs boils down to the task of shuffling the list of pubs such that the sum of the bottom row of the matrix above is minimised.

At this point I turn gladly back to the concorde solver I’ve discussed previously, which while a bit unnecessary for this simple problem, becomes very necessary for (much!) larger pub crawls.

The solution, crudely plotted with matplotlib, looks like this:

You can see that Google has decided we should be boarding the Picadilly line at least once, and getting the 8 and 25 buses at some point. Most of the route is fortunately walkable, definitely a bonus by the 7th or 8th pub.

The seasoned drinker will recognise the utility of a more informative and robust map. For this I turned to OpenStreetMap, which very generously allow you to export any portion of their map data. I used an excellent tool called Maperitive to download this data and convert it to .svg format which Illustrator can digest.

After some fiddling and cursing of my lacking design skills, I present the official Optimal Pub Crawl of Central London Map:

You should be able to cover the distance between the pubs in 45-60 minutes in total, which leaves a generous 10 hours of drinking, or 1 hour 15 minutes per pub.

This is plenty of time to take in the unique and ancient landscape of famous London pubs, savouring the surroundings, history, and yes, maybe even some of the beer too.

Happy crawling!

You can find the iPython notebook here:

Notebook on Github