A (near-)optimal tour of Aachen
Published:
When I lived in Aachen—a city brimming with history, charm, and yes, fountains—my friend and I made an ambitious summer plan: visit every fountain in town. A quintessential “summer” goal. But summer after summer, we let that plan evaporate. Now, years later, I’m finally solving this puzzle. Not just solving it—I’m turning it into a nice small computational adventure.
Aachen is famous for its fountains, each telling its own story. From the playful Puppenbrunnen to the iconic Elisenbrunnen, these waterworks are scattered throughout the city. They’re not just decorative but an integral part of the city’s identity. So, when I decided to “finally do this,” I thought, why not make it fun and nerdy as always? I’m not just someone who strolls from fountain to fountain—I have some computational science skills and coding expertise! Naturally, I devised a (near-)optimal solution to the Traveling Salesman Problem (TSP) to plan the route, even if I might never actually walk it!
As many of you might already know the TSP is a classic optimization problem where a "salesman" must visit \( N \) cities (or fountains, in our case), minimizing the total distance traveled and returning to the starting point. Formally, given a set of locations \( \{1, 2, \dots, N\} \) with distances \( d(i, j) \) between them, the goal is to minimize:
\[ \text{Total Distance} = \sum d(i, i+1) \]
Of course, the TSP is NP-complete and for larger \( N \) (which in our case is around 32), finding the exact solution via brute force is computationally infeasible (\( O(N!) \)). Instead, we settle for approximate solutions using heuristics like simulated annealing.
Now, to get the location of the fountains themselves, I fould a helpful list from Wiki Commons, where each fountain has its coordinates, name, and a photo. After some beautifulsoup parsing and cleaning (and nudging overlapping fountains by 10 m to make them unique), I fed the data into my code. (The overlapping fountains had to be moved to make sure the optimizer does not fail with zero distances between points). This is where I tried two types of distances the first being "as the crow flies" and the second the walking distance between these (to make sure such a tour is feasiable within a days effort). Now for each of these, I had to calculate the distance matrix between every pair of points, \( d(i, j) \). For this, I used the following methods:
Case 1: As the Crow Flies
This was the easy case and I used the Haversine formula:
\[ d(i, j) = 2r \cdot \arcsin\left(\sqrt{\sin^2\left(\frac{\phi_j - \phi_i}{2}\right) + \cos(\phi_i) \cos(\phi_j) \sin^2\left(\frac{\lambda_j - \lambda_i}{2}\right)}\right) \]where r is the Earth's radius, φ is latitude, and λ is longitude. This gives the “straight-line” distance between fountains.
Case 2: Walking Paths
This case is of course, much harder to calculate and I ended using the OpenRouteService API to compute the actual walking distances. The API returned a distance between two latitude longitude pairs and also a list of coordinates for the walking path. This makes the solution more realistic for those of us without wings. The idea and parts of the code for using the route service came from this blog here where a different optimizer is used for the same problem.
Both distance matrices were fed into a simulated annealing algorithm (thanks, Frigidum!). The algorithm mimics the cooling process of metals, finding a near-optimal route by progressively "cooling" the search space. I did battle with the original optimizer - concorde as in the blog but failed to get it to run successfully on my laptop so I had to resigned to using simulated annealing as mentioned in this Stack Overflow answer.
Coming to the actual results, you can explore it below with a dropdown menu allowing you to change from "As the Crow Flies" to "Walking Distance". You can hover over the markers to display some basic info about the fountins with an image from Wiki Commons. How did I choose the starting point I hear you asking? Well the starting fountain is chosen based on proximity to the geographic mean of all points—a little cherry on top. Now this solution of course, is great, its under 20 km so a days worth of walking would be enough to cover all of them within a day. (Also note that as we have are doing a round trip the total distance travelled does not depend on the starting point choosen!)
After solving this computationally, it’s time for the fun part: visiting Aachen again and walking the optimized route. All my friends (and frenemies! :D), if you’re reading this, pack your walking shoes. We’ve got an Aachen trip coming up next summer.
If any of you want to use this for your own geeky walking trips, then head over to my semi documented code on github, signup for your own OpenRouteService API and put this into your environment variable and setup a CSV file of your favourite places to visit. For those of you wanting to do this specific Aachen fountain trip, you can download the KML file which you can import into your google maps.
To view this route on Google My Maps:
- Download the file using the link above.
- Go to Google My Maps.
- Click on "Create a new map" and use the "Import" option to upload the file.
Of course, I should thank chatGPT for helping me with everything on this project (like many other projects!) with ideas, code, documentation, building, blog, README and so on.