Valhalla Open-Source-Routing-Engine:
Ein Vergleich zu anderen Lösungen
von Robert Klemm, WhereGroup
Infobrief 01 | 2020
In der Open-Source-Community gibt es viele Routing-Engines, die auf der Grundlage von OSM- oder eigenen Daten nutzbar sind. Zu den bekanntesten gehören die Routing-APIs GraphHopper und OSRM sowie die Datenbank-API pgRouting. Die etablierten Routing-APIs GraphHopper und OSRM existieren schon seit langem und erfreuen sich großer Beliebtheit. Auch die WhereGroup verwendet diese aktiv in verschiedenen Projekten.
Relativ neu bei den Routing-Engines ist das Open-Source-Projekt „Valhalla“ [1]. Nun stellt sich natürlich die Frage, was Valhalla im Vergleich zu den anderen Routing-Engines anbietet und welche Vorteile mit dem Einsatz verbunden sind. Im nachfolgenden Überblick werden wir daher auf die Vorteile von Valhalla eingehen und einen Vergleich zu den benannten Alternativen erstellen.
Valhalla ist eine Software zur Bearbeitung komplexer Routing-Anfragen. Mit ihr können nicht nur Erreichbarkeitsanalysen mit Isochronen-Berechnung durchgeführt werden, sondern auch innerhalb einer einzigen Anfrage Routings über verschiedene Verkehrsträger dynamisch erstellt werden.
Hervorzuheben sind folgende Services:
Routing-Service
Der Routing-Service berechnet mithilfe von Eingabepunkten, Routingprofilen (Auto, Fahrrad, zu Fuß) und den multimodalen Kombinationen eine Route. Valhalla bezieht die Daten aus OpenStreetMap und aus dem Transitland-Projekt.
Optimierter Routing-Service
Der Routing-Service löst das „travelling salesman problem“ (TSP). Hierzu wird die Zeit und Entfernung zwischen vielen Start- und Zielpunkten berechnet. Als Ergebnis wird eine optimierte Route zwischen den Standorten ausgegeben.
Abb. 1: Valhalla-Routing mit Frontend-Anbindung (Screenshot: Robert Klemm, WhereGroup)
Isochronen-Service
Der Isochronen-Service von Valhalla errechnet die Erreichbarkeiten von Orten in einer bestimmten Entfernung oder Reisezeit ausgehend von einem zentralen Ort. Valhalla kann dabei mehrere Standorte oder unterschiedliche Bewegungsprofile einfließen lassen.
MapMatching-Service
Der MapMatching-Service ordnet Koordinaten bekannten Straßen zu (reversed geocoding), sodass ein Pfad in eine Route mit Routing-Anweisungen verwandelt wird und die Attributswerte von dieser übereinstimmenden Linie mit OSM-Daten abgefragt werden
Höhenprofil-Service
Der Höhenprofil-Service ermittelt die Höhe entlang einer Strecke oder an bestimmten Punkten.
Transit-Service
Der Transit-Service ermittelt die Verfügbarkeit des Transits mit einem anderen Verkehrsmittel zu dem angegeben Standort.
Alternativrouten
Valhalla kann zur Laufzeit für alle Bewegungsprofile auch eine Alternativroute direkt auf der Karte anzeigen.
Dokumentationen
Zusätzlich bietet Valhalla für jeden API-Service eine umfassende Dokumentation mit Beispielen an [2].
Beispiel Service-Isochrone
Die Isochrone-API kann für eine Erreichbarkeitsanalyse für Auto, Fahrrad und Fußgänger genutzt werden (vgl. Abb. 2-4):
- 5 min = Farbe Grün
- 10 min = Farbe Gelb
- 20 min = Farbe Rot
Beispiel Service-Routing
Die Routing-API unterstützt bei Valhalla viele Parameter, die bei der Anfrage als zusätzliche Steuerung mit angegeben werden (vergl. Abb.1):
- alternative Routen
- Gewichtung für das allgemeine Routing
- zusätzliche Bewegungsprofil-Gewichtung
- Setzen von multimodalen Parametern
- Toleranzen für das Finden einer Route
Abb. 2: Isochrone für den Standort WhereGroup Berlin mit dem Auto (Screenshot: Robert Klemm, WhereGroup)
Abb. 3: Isochrone für den Standort WhereGroup Berlin mit dem Fahrrad (Screenshot: Robert Klemm, WhereGroup)
Abb. 4: Isochrone für den Standort WhereGroup Berlin als Fußgänger (Screenshot: Robert Klemm, WhereGroup)
Vergleich zwischen den Routing-Engines
Ein kurzer Vergleich zwischen den Routing-Engines zeigt im Überblick folgende Merkmale der einzelnen Lösungen:
- GraphHopper: genaue Route mit mehreren Live-Verkehrssituationen, monolithischen Daten, Berechnung und Nutzung von mehreren Profilen auf einem Graphen, multimodalem Routing und sehr hoher Leistung
- OSRM: genaue Route mit Live-Verkehr, monolithischen Daten, hohem Speicherbedarf, jedoch sehr hoher Leistung
- pgRouting: genaue Route mit mehreren Routingalgorithmen, individuelle Routenberechnung, multimodalem Routing (experimentell), skalierende Leistung bei zunehmender Datenmenge
Abb. 5: Robert Klemm (Foto: Foto Menke)
Fazit
Zusammenfassend lässt sich festhalten, dass Valhalla sich mit den etablierten Routing-Engines durchaus messen kann. Viele Features wie beispielsweise Matrix-Service, MapMatching, Isochrone, TSP und alternative Routen werden standardmäßig im Projekt mit geliefert. Ein großer Pluspunkt ist der zusätzliche Berechnungs-Parameter „Zeit“ für die Erstellung der Distanzmatrix und die zeitbasierten Routen, die jedoch nicht für alle Routingprofile nutzbar sind. Zum Vergleich: Dieser zusätzlich Parameter wird in OSRM nicht angeboten. Ein weiterer Vorteil Valhallas ist die Möglichkeit, Routinggraphen mit mehreren Profilen aufzusetzen - ähnlich wie es GraphHopper macht.
Dadurch ist eine Wartung und Erstellung von mehreren Routing-Graphen für die verschiedenen Routingprofile nicht notwendig.
Allerdings ist zu erwähnen, dass die Schnelligkeit der Berechnung bei großen Distanzen nicht so hoch ist wie bei den alternativen Lösungen. Je nach Anforderung muss man differenziert beurteilen, welche Routing-Engine eingesetzt wird. Wir empfehlen den Einsatz von Valhalla besonders bei Standortanalysen.
Weiterführende Links:
[1] Github: https://github.com/valhalla/valhalla
[2] Dokumentation: https://valhalla.readthedocs.io/en/latest/
>>> Zurück zum Inhaltsverzeichnis Infobrief 01 | 2020