The Twomlaut Tour of Germany

The Problem

It started with a Reddit post: someone mapped every city and town in Germany, color-coded by the number of umlauts in the name.^[1] Another user proposed the "Twomlaut Tour," a road trip visiting every place with two or more umlauts.^[2] A third asked the natural follow-up: what's the shortest route?^[3]

This is the kind of problem I can't resist. It sits right at the intersection of programming, optimization, and Unicode, three things I care about more than is probably healthy. I had to solve it.

Out of 93,000+ named places in OpenStreetMap's Germany extract, 652 contain at least two umlauts. Filtering out hamlets and villages leaves 45 cities and towns, a perfectly sized traveling salesman problem.

Finding the Cities

The starting point is a full OpenStreetMap extract of Germany (~4 GB PBF file). An Osmosis filter pulls out all nodes tagged as places (cities, towns, villages, hamlets), then a Python script walks the names looking for the three German umlauts: ä, ö, ü. Unicode normalization handles edge cases like decomposed forms (base letter + combining diaeresis). Of the 93,000+ named places, 652 have at least two umlauts. Filtering to place=city or place=town narrows the list to the 45 stops used in the tour.

The Approach

The solution has two stages. First, compute the real driving time between every pair of stops using Graphhopper, an open-source routing engine built on OpenStreetMap data. This produces a 45 × 44 = 1,980 pairwise cost matrix. Second, solve the TSP on that matrix to find the route that minimizes total driving time.

Let $N$ be the set of cities and $c_{ij}$ the driving time from city $i$ to city $j$.

Decision Variables

$x_{ij} = 1$ if the tour travels directly from city $i$ to city $j$.

Assignment Constraints

Each city has exactly one outgoing and one incoming edge:

Subtour Elimination (MTZ)

The assignment constraints alone allow disconnected loops: visiting Berlin → München → Berlin while separately cycling through Nürnberg → Würzburg → Nürnberg. The Miller-Tucker-Zemlin formulation eliminates subtours by introducing a continuous ordering variable $t_i$ for each city (except city 0, which is fixed as the start):

When $x_{ij} = 1$, the constraint forces $t_j \geq t_i + 1$, requiring the ordering to increase along every edge. Any cycle not passing through city 0 would need $t$ to increase around a loop, which is impossible. The result is a single connected tour with only $O(n^2)$ constraints instead of the exponentially many needed by explicit subtour enumeration.

Objective

Minimize total driving time:

For 45 cities, the MIP has roughly 1,980 binary variables, 44 continuous ordering variables, and about 2,000 constraints. The browser demo uses the same formulation with GLPK.js.

Results

CBC found a good route almost immediately, but proving it optimal was another story. The MTZ formulation's LP relaxation is notoriously loose, so the solver spent hours grinding down the optimality gap before finally certifying the answer: 42 hours and 19 minutes of driving across 45 stops, threading through Bavaria, Thuringia, Saxony, and back. A leisurely four-day road trip for the umlaut enthusiast.

The route was also computed against GADM administrative boundary data (the original poster's source), which produced a longer 49-hour route due to slightly different centroid locations. Three towns had centroids that didn't snap to nearby roads in the OSM data and had to be excluded.