Implementierung des Chinese Postman Problems im Valhalla Routing Engine

Im Anschluss an den vorangegangenen Artikel über Kadas Routing wollen wir nun die kürzeste Route für eine Kontrollfahrt über alle Strassen in einer ausgewählten Region berechnen.

Dieses Problem ist in der Graphentheorie als Chinese Postman Problem (CPP) oder Briefträgerproblem bekannt. Ziel ist es, den kürzesten Weg zu finden um sämtliche Kanten eines Graphen abzudecken.

Das CPP kann in polynomialer Zeit für gerichtete und ungerichtete Graphen gelöst werden. Für einen gemischten Graphen wird das Problem zu einem NP-Complete Problem.

Wie für die vorausgegangen Entwicklungen im Projekt Kadas Routing wurde Valhalla als Routing Engine genutzt und mit einer Lösung des CPP erweitert.

In dieser Implementierung arbeiten wir mit dem gerichteten Graphen, da er der Graphendarstellung in Valhalla für OpenStreetMap-Daten entspricht. Der CPP-Algorithmus wurde bereits für ideale Graphen und im Rahmen von wissenschaftlichen Studien entwickelt und kann mit dieser Visualisierung der Technischen Universität München (TUM) ausprobiert und getestet werden. Aktuell werden die folgenden 3 Algorithmen bentötigt um dieses Problem zu lösen: Floyd-Warshall Algorithmus, Hungarian Methode, und Hierholzer Methode. Für den Floyd-Warshall-Algorithmus verwenden wir den bereits in Valhalla integrierten Kostenmatrix-Algorithmus

Die grösste Herausforderung besteht darin, eine Lösung des CPP zu implementieren, die die Anwendung auf realen Strassennetzen ermöglicht. Theoretische Lösungen des CPP funktionieren nur für ideale Graphend.h. der Graph muss stark verbunden sein. Dies ist in der realen Welt jedoch nicht oft der Fall, so dass wir den theoretischen Algorithmus in mehreren Punkten verbessern und ergänzen mussten. Ein Beispiel hierfür ist der relativ häufig auftretende Fall, dass man den zu befahrenen Bereich verlassen muss, um Teile des Netzwerks zu besuchen, die von innerhalb des definierten Gebiets nicht erreichbar sind (z.B. Einbahnstrassen im Randgebiet).

Letztendlich ist es uns gelungen, einen funktionierenden Prototyp des CPP in Valhalla zu erstellen. Der Benutzer kann eine Reihe von Angaben vor der eigentlichen Berechnung festlegen: das zu befahrene Gebiet, Sperrzonen (Gebiete die umfahren werden müssen) und den Fahrzeugtyp. Als Ergebnis wird eine Route mit Turn-by-Turn-Navigation zurückgegeben, vergleichbar mit einem Standard Routing Algorithmus. Die berechnete Route also auch für die Navigation verwendet werden.

Den nächsten Schritt stellt die Einbindung dieser Funktion in den Master Branch von Valhalla dar, damit diese Neuentwicklung von der Community weiter genutzt und getestet werden kann.

Wir möchten uns bei dem Kunden und Sponsor dieses Projektes Armasuisse bedanken.