Every Street in Offenbach by Bike

New year’s resolution: more exercise? The idea here is a single bike route that covers every street in Offenbach at least once while keeping redundant riding to a minimum. This is the Chinese Postman Problem.

• Street network: ~148 km
• Optimized route: ~195 km (32% redundancy)
• At 15 km/h average: ~13 hours
• Start/end: Wilhelmsplatz

How it works

A graph where every node has even degree has an Eulerian circuit – a closed walk that traverses every edge exactly once. Real street networks don’t have that property, so the trick is to duplicate a minimal set of edges until all nodes become even-degree. Then the Eulerian circuit gives us the route.

The street network comes from OpenStreetMap, filtered to Offenbach’s city boundaries:

import networkx as nx
import json
from shapely.geometry import Polygon, Point

of_boundaries = json.load(open("of_boundaries.json", "r"))
poly = Polygon(of_boundaries)

def point_in_polygon(p):
    point = Point(p)
    return point.within(poly)

After augmenting the graph, NetworkX handles the rest:

circuit = list(nx.eulerian_path(G_euler))

Since this uses the car street network, a follow-up with Offenbach’s bike path network would probably look quite different.