You want to go for a drink but don't know the shortest way to visit all pubs in your hometown? Not anymore! Read on and discover the mathematically shortest path to visit 237 pubs in Ghent, Belgium.

First I needed a list of all pubs. Find a website listing them. Write a small Python script to scrape the website and save all addresses in a list. Easy. A little Javascript to retrieve the walking distance between each two listed pubs from Google Maps. Make it recursive with a small delay as Google doesn't like 30.000 requests at once. Let it run overnight. Perfect. Convert the resulting list of distances into a huge matrix and run this input through the Concorde TSP solver. Extend the Javascript to display the resulting loop on a map. Let's get to work.

Also why is this important? Because time is money. Say you need to solder 1000 connectors on a circuit board. If your printerhead can do this by moving a shorter distance moving between the connectors, you can print more circuit boards in the same time. Profit!

Shortest possible walking route visiting 237 pubs

Walking tour from Google maps

My tracked walk, Feb 15th

After a few days of coding, 29993 meters to visit all known 237 pubs. I also borrowed a GPS tracker from a friend and actually went for a walk following the shortest loop. Because why not.

A list of all pubs in Ghent does not seem to exist anymore, but a few years back there was a website caféplan.be which listed a lot of pubs in the major Flemish university cities. Of course I saved the site offline back then because I knew future Sander would need it some day. The page is from 2017 listing 237 pubs. A small Python script scraps the offline page and dumps all the pub info in a json file.

{"index":158,"name":"Petrus","address":"Sint-amandstraat 15, 9000 Gent, Belgie","coordinates":{"latitude":51.0434944,"longitude":3.7246773}},
{"index":159,"name":"Pi-nuts","address":"Graaf arnulfstraat 8, 9000 Gent, Belgie","coordinates":{"latitude":51.0434936,"longitude":3.7254492}},
{"index":160,"name":"Pink flamingo's","address":"Onderstraat 55, 9000 Gent, Belgie","coordinates":{"latitude":51.0559068,"longitude":3.7250956}},
{"index":161,"name":"Plan b","address":"Verlorenkost 17, 9000 Gent, Belgie","coordinates":{"latitude":51.0465501,"longitude":3.7211557}},

We can't just calculate the distance from the coordinates though, as we can't walk through buildings. We want the distance as we would actually walk. To prove my point, I did both. Spherical distances and walking distances from Google Maps after writing and running a script overnight.

Solution from coordinates (geographical distance)

Solution from distance matrix (walking distance)

Great. Using these distances, I created a TSPLIB file with a 237 x 237 distance matrix as input file for the Concorde TSP solver. The resulting optimal tour was then used as input for another piece of Javascript to visualise the 237 separate subtours as one closed loop covering all pubs. That's all for now.