Visiting every pub in Dublin

In our last blog post we elaborated the problem of finding a route through Dublin without passing by any Pub. Rory gave us the idea for this, and now again, pointed us to an article reporting that recently there was a Japanese man trying to visit each and every pub to drink a pint of Guinness.

From ‘avoid pubs’ to ‘visit all pubs’

Thus, we were keen to see how the route looks if we reformulate the problem from “avoiding pubs” to a problem of “visiting all pubs”. It seems to be a similar problem just do the “inverse”, but it is not. This is the classical traveling salesman problem in contrary to a least cost path problem. The Japanese man called Abe used ‘The Dublin Pub Spotters Guide’ by Mac Maloney as pub guide. We do not have this guide. However, we retrieved 226 pubs located in the center of Dublin from OpenStreetMap via overpass. Additionally, we assumed that Abe started his journey at Connolly station, i.e. he walked all the way and stayed 30 minutes in every pub. Here is the problem on a map:

And what is the solution? To visit every pub exactly once he needs to walk 38 kilometers, i.e. approximately 7 hours and 46 minutes (neglecting the fact that the more beer he has, the slower he is able to walk from one pub to another). Considering that he stays in each pub 30 minutes, Abe’s pub project takes 5 days, 46 minutes in total.

How many days a more realistic pub journey will take?

Apart from that making the Guinness project in four weeks is ambitious, visiting all pubs in a row is quite an additional challenge ;). Thus, to make it more realistic we reformulated the problem so that we give Abe some time to recover, i.e. we only give him 5 hours and 30 minutes time per day for his pub journey. Thus he needs to start at 6pm from Connolly station. By 11:30pm he needs to be back again. This is also in line with the opening hours of most of the pubs. The problem then turns into a vehicle routing problem with time restrictions where we not only want to find the best routes, but also to determine the number of days the pub project takes. Lets look at our solution. It takes 27 days to visit all pubs, 152 kilometers need to be walked corresponding to 1 day, 6 hours and 27 minute walking time. To illustrate this, look at the following figures showing the routes of day 1, 9 and 21. On the right side of each figure, one can see the highlighted route along with the pub locations marked in red. On the left side, there is a table showing the arrival and departure times for each pub as well as the cummulated distances.

These last pictures are from our route debugger, which is available in our dashboard and makes playing around with our API very simple. If you want to learn more, just visit GraphHopper.com and play with our live examples!

Discussion and comments happened at hackernews.