Routenplanung mit OpenStreetMap

last updated 2019-09-06

Dieser Blogeintrag beschreibt wie Routenplanung :running: :bike: :car: auf Grundlage von OpenStreetMap(OSM) Daten funktioniert. Zuerst werden die Grundlagen erklärt und im Anschluss die Programme GraphHopper, pgRouting und der Web Service OpenRouteService vorgestellt.

Bevor wir direkt auf die Routenplanung eingehen noch ein kurzer Kommentar zur Datenqualität von OpenStreetMap. Die Daten werden von Freiwilligen erhoben und sind unter einer offenen Lizenz (ODbL) verfügbar. Die Qualität der Daten in OpenStreetMap ist sehr heterogen. Manche Regionen sind besser kartiert als andere. Aber auch die Vollständigkeit der einzelnen Datenkategorien wie Straßen oder Geschäfte ist stark unterschiedlich verteilt. Im Allgemeinen kann man aber davon ausgehen, dass Straßen und Wege in OpenStreetMap am besten von allen Kategorien kartiert sind. Einerseits ist OpenStreetMap wie der Name schon sagt für Straßen erfunden worden. Andererseits kann man Straßen sehr leicht via GPS-Track oder Satellitenbild digitalisieren. Da OSM bereits häufig für Routinganwendungen genutzt wird werden auch etwaige Fehler schnell entdeckt und korrigiert. OpenStreetMap kann also im Bereich der Straßen durchaus mit kommerziellen Datenanbietern konkurrieren und ist oftmals sogar besser.

Nun aber zur Routenplanung. Programme die Routen berechnen können werden Routing Engines genannt. Diese funktionieren im Prinzip wie folgt: es wird ein OSM-Datensatz eingelesen (“geparst”) und in einen Straßengraphen umgewandelt. Dabei werden Straßensegemente in Kanten (“edges”) und Kreuzungen in Knoten (“nodes”) umgewandelt. Jede dieser Kanten hat eine Gewichtung. Meistens ist das die Distanz oder die Reisezeit. Mit diesem Straßengraphen können Algorithmen wie Dijkstra oder A* durch die Minimierung der Gewichtungen den kürzesten Weg zwischen zwei Punkten finden.

Um die Routenplanung für unterschiedliche Transportmittel wie Auto, Fahrrad oder Fußgänger anzupassen, müssen die Gewichtungen der Kanten entsprechend geändert werden. Jedes Transportmittel (im Folgenden als Routingprofil bezeichnet) kann sich nur auf bestimmten Typen von Straßensegmenten bewegen. Ein Auto kann beispielsweise nicht auf dem Fußweg fahren, ein Fußgänger darf nicht auf die Autobahn. Jedem Routingprofil stehen also nur eine Teilmenge aller Straßensegmente zu Verfügung. Zusätzlich wird jedes Straßensegment mit einer Gewichtung versehen die spezifisch für das jeweilige Routingprofil ist. Ein Auto braucht beispielsweise für einen Abschnitt weniger Zeit als ein Fahrrad.

Kanten können auch unterschiedliche Gewichtungen für jede Richtung haben. Beispielsweise dauert das Hinauffahren eines Hügels mit einem Fahrrad viel länger als das Herunterfahren. Für die Gewichtung der Kanten können sehr viele Eigenschaften in Frage kommen, etwa CO2-Ausstoß, die Schönheit der Landschaft oder Lärm. Dies würde jeweils umweltfreundliche, schöne oder stille Routen erzeugen.

Es gibt einige Routingengines die man lokal auf einem Computer installieren kann: GraphHopper, OSRM, Valhalla, pgRouting, OpenTripPlanner. Diese Präsentation (Video, Slides) von Frederick Ramm vermittelt einen guten Überblick und Vergleich. In diesem Blogpost wird allerdings nur GraphHopper und pgRouting genauer beleuchtet.

GraphHopper

GraphHopper ist eine Java Bibliothek das auch als eigenständiges Program laufen kann. Die Installation mit diesem Quickstart geht verhältnismäßig leicht. In den Standardeinstellungen wird allerdings nur der Straßengraph für Autos berechnet. Weitere Profile und Einstellungen können jedoch in der .properties Datei aktiviert werden. Sobald das Programm läuft wird ein lokaler Routing Service auf Port 8989 gestartet. Dieser kann entweder mit einer lokalen Webanwendung getestet werden. Diese sieht ähnlich aus wie diese Beispielseite.

Die Routen können allerdings auch automatisiert über eine Schnittstelle (API) berechnet werden. Dazu werden die benötigten Argumente (Startpunkt, Endpunkt, Routingprofil, …) in einer URL angegeben. Siehe folgendes Beispiel:

localhost:8989/route?
  point=53.525615%2C15.514755&
  point=53.540307%2C15.46875&
  vehicle=car&
  weighting=fastest&
  elevation=true

Als Antwort liefert die Schnittstelle eine JSON-Datei mit den gewünschten Informationen. Prinzipiell kann die Schnittstelle mit jeder üblichen Programmiersprache angesprochen werden, allerdings gibt es schon einige vorbereitete Vorlagen. GraphHopper stellt einige Routingprofile bereit. Man kann auch eigene hinzufügen, dies ist jedoch relativ aufwändig.

Alles in allem eignet sich GraphHopper gut um mit überschaubarem Aufwand einen lokalen Routingdienst zu betreiben. Es ist sehr schnell und hat eine benutzerfreundliche Schnittstelle. Man kann sogar Routinggraphen für den ganzen Planeten erstellen. Dazu ist jedoch sehr viel RAM notwendig.

pgRouting

pgRouting hat im Gegensatz zu GraphHopper eine andere Zielsetzung. Es ist eine Erweiterung der PostgreSQL Datenbank und baut auf PostGIS auf. Für die Benutzung von pgRouting sind deshalb grundlegende Kenntnisse in der Abfragesprache SQL notwendig. Auf der Webseite von pgRouting gibt es einen Workshop der einen Einsteig in die Software bietet. Die Linux Distribution OSGeoLive hat pgRouting von Haus aus schon installiert und bietet einen Testdatensatz an.

pgRouting besteht im wesentlichen aus grundlegenden Routingfunktionen. Routingprofile fehlen allerdings völlig, diese müssen bzw. können komplett selbst erstellt werden. Deshalb muss man sich vorher im Klaren sein was man möcht und kann sich dann eine maßgeschneiderte Routinganwendung bauen.

Mit pgRouting kann man Isochronen berechnen. Das ist grob gesagt ein Algorithmus der alle Punkte innerhalb eines bestimmten Kostenlimits zurückliefert. Mit Isochronen kann man beispielsweise die Frage beantworten wieviele Supermärkte innerhalb eines 25 minütigen Umkreises liegen.

Das für pgRouting zugrundeliegende Straßennetzwerk ist in der Postgres Datenbank gespeichert und ist dynamisch veränderbar. Es können sowohl Geometrien als auch Gewichtungen verändert werden. Das eignen sich besonders für Fälle bei denen dynamische Daten wie Wetter oder Verkehr in die Routenplanung miteinbezogen werden sollen.

Beispiel Abfrage (Quelle) :

SELECT * FROM pgr_dijkstra(
    'SELECT gid AS id,
         source,
         target,
         length AS cost
        FROM ways',
    9411, -- source id
    3986, -- target id
    directed := false);

Die obenstehende Abfrage zeigt grundlegende Routingfunktionen auf. Die Länge der Straßensegmente wird als Kosten für das Routing verwendet. Dies kann allerdings zu allem möglichen anderen geändert werden, beispielsweise Lärmpegel der Straße oder CO2-Ausstoß. Das Ergebnis der Abfrage ist eine Liste von allen durchlaufenden Kanten und Knoten. Diese können dann ausführlich analysiert werden. Um allerdings die Geometrie der gesamten Route zu erhalten ist es notwendig die Geometrien der einzelnen Knoten mithilfe einer weiteren Funktion anzufügen (Join in der Datenbank).

Der Workshop von pgRouting stellt bereits einige nützliche Funktionen bereit. Für QGIS gibt es ein Plugin namens pgRoutingLayer. Damit kann man über eine Benutzeroberfläche (GUI) Einstellungen vornehmen und sich das Ergebnis gleich als Kartenebene (Layer) darstellen lassen.

Um pgRouting mit OSM Daten zu nutzen steht das Kommandozeilen Programm osm2pgrouting zu Verfügung. Jedoch können auch jegliche anderen räumlichen Datensätze verwendet werden. Dies ist allerdings mit mehr Aufwand verbunden. Dieser Post beschreibt beispielsweise wie man Daten von einem Shapefile importieren kann. Dank der Flexibilität von pgRouting ist man nicht nur auf Straßennetzwerke beschränkt. Es ist ohne Probleme möglich Routinggraphen aus anderen Netzwerken wie Eisenbahnschienen oder Flusssystemen zu bauen.

Insgesamt eignet sich pgRouting gut um spezialisierte Routinganwendungen zu bauen, da man sehr viele Einstellungen vornehmen kann und ein sehr ausführliches Ergebnis bekommt. pgRouting ist allerdings im Vergleich zu GraphHopper relativ langsam und ausserdem etwas komplizierter zum aufsetzen. Typischer Anwendungsfälle von pgRouting wären die Analyse von Straßennetzwerken, Darstellungen oder spezialisierte Routingdienste mit überschaubar vielen Anfragen.

OpenRouteService

Es gibt zahlreiche Routinganbieter im Internet. Beispielsweise GraphHopper API, Mapbox oder OpenRouteService. Diese bieten eine Schnittstelle (API) an. Somit muss erstmal nichts lokal installiert werden, allerdings muss man für Routinganfragen bezahlen.

Der Dienst OpenRouteService wird von der Universität Heidelberg betrieben und bietet eine Vielzahl verschiedener Routingprofile mit denen neben klassischen Routen auch Isochronen berechnet werden können. OpenRouteService kann auf verschiedene Arten genutzt werden: über die Webseite maps.openrouteservice.org, die Schnittstelle (API) und über das QGIS Plugin ORStools welches im Hintergrund auch auf die API zugreift. Mit diesem Plugin bekommt man die Geometrie der berechnet Route oder Isochronen direkt als Layer in QGIS und kann von dort weiter ausgewertet und verarbeitet werden.

Die Benutzung eines Webdienstes wie OpenRouteService is relativ leicht und hat den großen Vorteil dass das zugrundeliegende Straßennetzwerk regelmäßig vom Anbieter aktualisiert wird. Deshalb basieren die berechneten Routen immer auf den neuesten Daten. Wenn man hingegen seinen eigenen Routingdienst betreiben möchte muss man auch das Straßennetzwerk regelmäßig aktualisieren, was wiederum mit erheblichen Mehraufwand verbunden ist. Jedoch hat natürlich auch die Nutzung eines Routingdienstes wie OpenRouteService Nachteile. Einerseits ist man immer von einer stabilen Internetverbindung abhängig, andererseits muss man für die berechneten Routen bezahlen.

Weiterführende Links

Hier noch einige Verweise zu Webseiten mit ähnlichen Themen:

• Topi Tjukanov hat viel mit GraphHopper und pgRouting gearbeitet und darüber geschrieben
• Anita Graser hat einige Beiträge zu Routenplanung geschrieben und geht dabei hauptsächlich auf pgRouting ein
• auf Digital Geography sind einige Beitrage zum Thema Routenplanung
• Die Seite über “Routing” im OSM-Wiki - deutsch - englisch