Wanderungen plane ich inzwischen meistens digital auf einer Webkarte und klicke mir dabei aus einzelnen Punkten eine Route zusammen. Aber was passiert dabei eigentlich im Hintergrund? Es wird zwischen einzelnen Punkten die kürzeste Verbindung auf Wegen berechnet. Zeit, sich das Thema Routing einmal genauer anzusehen. Ich beschreibe hier die Möglichkeiten von Routing anhand der Software Graphhopper, welche in der Regel mit OpenStreetMap-Daten arbeitet. Freie Alternativen mit ähnlichen Funktionen sind OSMR und Valhalla.
Was macht eine Routingsoftware?
Die Hauptaufgabe einer Routingsoftware ist in der Regel die Berechnung einer schnellsten oder kürzesten Strecke. Nun bewegen wir uns meistens nicht querfeldein fort, sondern nutzen verschiedene Arten von Wegen je nach unserer Art der Fortbewegung: Auto, Fahrrad oder zu Fuß. Damit diese Wege berücksichtigt werden können, müssen diese erfasst und in einer graphenähnlichen Struktur vorliegen, um darauf mittels Algorithmen Routen berechnen zu können. Als Datenquelle wird häufig OpenStreetMap verwendet, das die notwendigen Geodaten bereitstellt, welche erst noch in einen Graphen umgewandelt werden müssen. Die Daten sind dabei nicht nur ein Graph, dessen Knoten mittels Kanten verbunden sind, sondern dessen Knoten auch noch räumlich verortet sind. Die Kanten haben wiederum bestimmte Eigenschaften wie einen Wegtyp und unter anderem eine maximale Geschwindigkeit als Eigenschaft.
Auf Basis des Graphen und der darin gespeicherten Informationen stellt die Routingsoftware eine Route zusammen. Dafür wird zunächst vom Startpunkt der nächstliegende Punkt auf dem Graphen gesucht (Einrasten/Snapping) und anschließend die Route berechnet. Wie genau die Route berechnet wird, hängt vom gewählten Profil ab. Typische Beispiele sind hier verschiedene Arten der Fortbewegung (Auto, Fahrrad, …). Die Route wird anschließend visuell auf einer Karte ausgegeben, Navigationsanweisungen ausgegeben und wichtige Informationen wie Dauer und Distanz ausgegeben.
Routenplanung mittels Graphhoper
Graphhopper selbst bietet eine kostenlose Vorschau auf die Möglichkeiten der Software auf seiner Webseite. Hier kann man sich für verschiedene Fahrzeuge und Fortbewegungsarten Routen mittels vordefinierter Routingprofile berechnen und das Ergebnis visualisieren lassen. Diese Funktionen sind allgemein üblich und finden sich bei allen Routingservices wieder. Spannender ist, das Diagramm unten rechts; hier lassen sich verschiedene Aspekte der Route darstellen: unter anderem Straßentyp, Gefälle, maximal mögliche Geschwindigkeit und die in der Berechnung verwendete durchschnittliche Geschwindigkeit. Die Straßentypen und Oberflächen stammen von OpenStreetMap. Die verwendeten Werte und was diese bedeuten, kann man im OpenStreetMap-Wiki nachlesen. Die angezeigten Höheninformationen stammen aus einem Höhenmodell und werden auf den Graphen übertragen.
Wer also mehr über seine Route wissen möchte, kann hier bereits spannende Einblicke gewinnen. Das Schöne an OpenSource ist ja, dass man auch nachschauen kann, was im Hintergrund passiert. Die verschiedenen Routingprofile und deren Konfiguration finden sich bei Github wieder. Was hier genau passiert, erklärt ein Beitrag in der Dokumentation des Graphhoper Repository. So kann man beispielsweise aus der Konfiguration für LKWs (truck.json) unter dem Punkt „priority“ herauslesen, das private Straßen und für LKWs gesperrte Straßen nicht für die Routen infrage kommen, was durch den Wert „0“ ausgedrückt wird. Des Weiteren, dass nur Straßen mit einer zulässigen Fahrzeugbreite von mehr als drei Metern und einer Höhe von mindestens 4 Metern berücksichtigt werden. Die Geschwindigkeiten werden unter „speed“ und den Einfluss der Distanz unter „distance_influence“ prametrisiert.
{
"distance_influence": 1,
"priority": [
{ "if": "car_access == false || road_access == PRIVATE || hgv == NO", "multiply_by": "0" },
{ "if": "max_width < 3 || max_height < 4", "multiply_by": "0" }
],
"speed": [
{ "if": "true", "limit_to": "car_average_speed * 0.9" },
{ "if": "true", "limit_to": "95" }
]
}
Graphhopper Routingprofile anpassen
Ein sehr cooles Feature von Graphhopper ist das Anpassen von Routingprofilen aus dem Webinterface heraus, über die Option „Custom Model“, welche sich hinter dem Zahnrad links der Routingprofile verbirgt. Hier finden sich verschiedene Beispiele zum Ausprobieren, wie sich das bestehende Routingprofil adaptieren lässt. Das Lesen der Dokumentation der Routingprofile erleichtert das Verständnis der Optionen. Im folgenden Beispiel habe ich die Höhenbeschränkung für LKWs auf fünf Meter gesetzt, um die Auswirkung zu demonstrieren – es ergibt sich eine vollkommen andere Route. Das Feature ist ausgesprochen praktisch, wenn man nur kleine Änderungen an einem Routingprofil haben möchte.
-
- Normale LKW-Route
-
- LKW-Route für mehr als fünf Meter höhe
Hier noch ein Beispiel, wie man sich das Fußgängerrouting anpassen kann – wenn man die Wege ohne Wegmarkierungen geringer gewichtet (also mit einem Wert kleiner als eins multipliziert), dann werden automatisch die markierten Wege bevorzugt, aber trotzdem andere Wege noch genutzt (ein Verbot wäre eine Multiplikation mit null). Des Weiteren werden noch asphaltierte und gepflasterte Wege in gleicher Weise herabgestuft und damit in der Route eher gemieden. Je höher der Werte bei „distance_influance“ ist, desto wahrscheinlicher wird sich eine kurze Route ergeben. Ein wenig mit den Parametern zu spielen wird hier helfen, einen guten Wert zu finden. Zuletzt noch ein Beispiel für die Limitierung der Geschwindigkeit: man kann einen maximalen Wert in Kilometer pro Stunde angeben. Einfach so oder auch in Abhängigkeit von Steigung oder Beschaffenheit der Wege. Damit kann man dafür sorgen, dass sich realistische Wegzeiten ergeben.
{
"distance_influence": 15,
"priority": [
{
"if": "foot_network == MISSING",
"multiply_by": "0.5"
},
{
"if": "surface == ASPHALT || surface == PAVED",
"multiply_by": "0.5"
}
],
"speed": [
{
"if": "true",
"limit_to": "3"
}
]
}
Graphhopper selbst lokal aufsetzen
Alle Optionen und Möglichkeiten bekommt man, wenn man sich die Software selbst lokal einrichtet, was erstaunlich einfach ist! Graphhopper ist in Java implementiert und bringt alles Notwendige in einer Datei mit. Es braucht dazu nur wenige Schritte:
- Eine Java Runtime Environment installieren, zum Beispiel von hier.
- Ein Graphhopper Release herunterladen.
- OpenStreetMap-Daten im PBF-Format herunterladen, zum Beispiel von der Geofarbik oder einem eigenen Ausschnitt.
- Alles mit einer Konfigurationsdatei ( Graphhopper Minimalkonfiguration ) in einen Ordner legen.
- Name der PFB-Datei in der yml-Datei anpassen und über die Kommandozeile starten.
Der Befehl zum Starten lautet:
java -jar graphhopper-web-9.1.jar server config-minimal.yml
Anschließend ist nach kurzer Zeit lokal unter der URL http://localhost:8989/maps/ der Graphhopper erreichbar. Zugegeben, die genaue Zeit hängt von der Größe der PBF-Datei ab. Ich würde empfehlen, mit einer kleinen Region zu beginnen und nicht gleich ein ganzes Bundesland zu verwenden, da der Aufbau des Graphen einen Moment dauert.
Anzeige einer lokal berechneten Karte und des Graphen
In meinem Beispiel sieht es dann wie in der Abbildung oben aus, man kann Routen für Fußgänger und Autos berechnen. Über das Kartenmenü in der rechten oberen Ecke kann man noch weitere Daten sich anzeigen lassen, wie den Graphen oder die Berechnung der „Urban Density“. So kann man sich unmittelbar die Gewichtung sowie die Eigenschaften der einzelnen Kanten anschauen und an einem Routingprofil basteln. Die „Customs Models“ sind mit meiner Beispielkonfiguration ebenfalls möglich. Die möglichen Werte für den Graphen lassen sich über den Endpunkt http://localhost:8989/info abrufen. Wer sich weiter mit der API beschäftigen möchte, findet in der Dokumentation dazu mehr. Natürlich lassen sich auch in der Konfiguration noch viele Einstellungen treffen, wie in einem Beispiel recht ausführlich erklärt wird.
Fazit
Graphhopper ist ein mächtiges Werkzeug zum Routing, das man sehr einfach selbst nach seinen Bedürfnissen anpassen kann. Die Installation auf dem eigenen Rechner ist erstaunlich simpel und ermöglicht, sich tiefer in die Materie einzuarbeiten. Im Stillen ist die Software an vielen Stellen mit OpenStreetMap-Daten im Einsatz: ob es um die Zustellung von Paketen, die Erreichbarkeitsanalysen oder die Einsatzplanung von Einsatzmitteln in Rettungsleitstellen geht.
Schreibe einen Kommentar