Ghent Bar Crawl

Solving the Travelling Salesman Problem for pubs in Ghent · February 2020

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. That wasn't too bad.

29993 meters to visit all 237 pubs.

Then things got a bit out of hand and I borrowed a GPS tracker from a friend to go on a 30km walk through Ghent. On a Saturday. Not recommended. I took a few wrong turns but overall I think theory and practice look pretty similar. No time to stop for drinks though. Sad face.

Techy details

Why is this problem so important? It's a famous example of the P vs NP millenium problem. Finding the shortest path also has major economic value, not only when actual travelling. 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. Profit!

Addresses

A list of all pubs in Ghent does not seem to exist but a few years back, there was a website caf├ęplan.be which listed a lot of pubs in the major Flemish university cities. Back then, I saved the Ghent page offline because you never know if you might need it to solve a mathematical problem somewhere in the future. The page is from 2017 listing 237 pubs.

A small Python script scraped the offline page and dumped 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}},
Walking distances

Why not just use the coordinates of each pub as I already had those? Because the shortest distance in a straight line (geographical distance, yes I know it's not truly straight as the earth is not flat but on such a small scale we can neglect the curvature of the earths surface) does not mean it is also the shortest when following actual roads.

To prove this, I also calculated the shortest route using coordinates rather than the distance matrix as input. Even though the geographical distance is slightly shorter using coordinates, the actual walking distance is quite a bit longer. Glad the math worked out. The difference in solution is seen in the images below.

InputGeographicalWalking
Coordinates23856 m32889 m
Distance matrix24404 m29993 m
Visualisation

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 it. Fun project to work on. Especially liking the visualisation of different tours.