Als Teil des Projekts KADAS-Routing wurde der Routing Engine Valhalla mit einer Lösung des Chinese Postman Problems (CPP) erweitert. So kann nun innerhalb eines definierten Polygons die effizienteste Route, um sämtliche Straßen und Wege im Gebiet zu befahren, berechnet werden.

Das CPP ist ein bekanntes Problem aus der Graphentheorie, wo es gilt jede Kante in einem Graphen zu besuchen und dabei die zurückgelegte Strecke zu minimieren. In der Theorie kann ein Graph entweder gerichtet, ungerichtet oder gemischt sein.

In dieser Implementierung wurde das CPP für gerichtete Graphen implementiert, da dies der Darstellung von Graphen in Valhalla und der Datenstruktur von OpenStreetMap (OSM) entspricht. Letzteres bildet die Datengrundlage für die Berechnung der CPP Route.

Das CPP wird über folgende separate Algorithmen abgebildet: der Floyd-Warshall Algorithmus, die Hungarian Methode, und die Hierholzer Methode. Nach erfolgreicher Implementierung der theoretischen Codebasis des CPP, bestand die größte Herausforderung darin die Routenberechnung unter Verwendung von Straßennetzen aus der Praxis (OSM) lauffähig zu machen.

Ein zentrales Problem mit der Implementierung des theoretischen CPP besteht darin, dass bei realen Graphen nicht immer jede Kante von allen anderen Kanten erreichbar ist. Daher mussten diverse Erweiterungen vorgenommen werden um die Berechnung einer CPP Route unter Verwendung von OSM Daten zu ermöglichen. So sind zum Beispiel Innerhalb eines größeren Gebiets selten sämtliche Straßenabschnitte ausschließlich über die im Gebiet lokalisierten Straßen erreichbar. Häufig muss das Gebiet verlassen werden um diese sonst nicht zugänglichen Teiles des Wegenetztes zu befahren.

Letztendlich konnten wir einen funktionsfähigen Prototypen des CPP in Valhalla erstellen. Neben der Funktion das zu befahrene Gebiet frei zu wählen, können auch Sperrzonen definiert werden. Nach der Wahl des Fahrzeugtyps (PKW, Fahrrad, Fußgänger, etc.) kann die CPP Route berechnet werden, die zudem eine Turn-by-Turn-Navigation mitliefert.

Wir bedanken uns bei dem Auftraggeber und Sponsor Armasuisse.