Routenplanung mit OpenStreetMap

Routenplanung mit OpenStreetMap

Dieser Blogeintrag beschreibt wie Routenplanung ­čĆâ ­čÜ▓ ­čÜŚ 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.

/img/edge_node_route.png

Knoten (Kreuzungen) und Kanten (Stra├čensegmente) und eine Beispielsroute

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.

/img/graphhopper_webapp.png

Screenshot GraphHopper Webanwendung

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.

/img/pgrouting_example.jpg

Die Isochronen Berechnenung mit pgRouting liefert jeden einzelnen Knoten

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.

/img/ors_isochrone.png

Das QGIS Plugin ORStools greift auf OpenRouteService zu

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.

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
  • Road to Rome ist ein Projekt von Moovel Lab. Es werden Routen durch viele L├Ąnder und Kontinente dargestellt.