pgRouting - Eine Einführung

am

Ein Gastbeitrag vom Team Wahre Logistik
Lukas Felzmann, Alexander Opris, Felix Mayer

Datum der Originalveröffentlichung Jan 20. 2023; 6 min read

Weitere Beiträge vom Team Wahre Logistik

Ob Dijkstra, A-Star oder Johnson-Algorithmus, pgRouting reichert gewöhnliche Postgres-Datenbanken mit zahlreichen Funktionalitäten rund um's Routing und Netzwerkanalysen an. Und das Beste: pgRouting ist Open Source. Das nehmen wir zum Anlass, um einen kleinen Leitfaden für pgRouting-Einsteiger zu schreiben. Hierbei erklären wir im Wesentlichen ...

  • ... wie man OSM-Daten in eine Postgres-Datenbank importiert.
  • ... wie man Routen berechnet.
  • ... wie man Routen visualisieren kann.

Voraussetzungen

Zunächst ein paar Voraussetzungen, die erfüllt sein müssen, bevor man mit diesem Tutorial beginnt. Folgende Tools müssen bereits installiert sein:

  1. 1. Postgres
  2. 2. PostGIS und pgRouting
  3. 3. R samt der folgenden Packages:
    • DBI
    • odbc
    • leaflet

Sollte die Installation von pgRouting Schwierigkeiten bereiten, so kann man in Windows auch auf den Application Stack Builder zurück greifen. Hier kann man sich in einer GUI benötigte Anwendungen und Extensions "zusammenklicken". Im Falle von pgRouting einfach das PostGIS Bundle unter Spatial Extensions installieren. Der dritte Punkt (also R) ist nur dann relevant, wenn man Routen visualisieren möchte.

Setup

Es wird empfohlen pgRouting nicht auf der Standard-Datenbank postgres zu verwenden. Deshalb legen wir eine separate Datenbank auf unserem Postgres-Server für Routing-Zwecke an. Diese nennen wir routing_db . Auf dieser müssen wir PostGIS und pgRouting noch aktivieren. Hierzu führen wir folgende SQL-Befehle aus:

CREATE EXTENSION PostGiS;

CREATE pgRouting;

Import der OpenStreetMap-Daten

Download: 

Unsere Datenbank ist also schonmal bereit. Um jetzt Routen zu berechnen, fehlt aber noch eine entscheidende Zutat: Kartendaten. In diesem Tutorial verwenden wir Daten von QpenStreetMap (OSM). Es stehen verschiedene Mirror zu Verfügung, um OSM-Daten herunterzuladen. Wir verwenden Geofabrik. Geofabrik bietet die Möglichkeit unterschiedlich große Auszüge aus den weltweiten OSM-Daten herunterzuladen (Kontinente, Länder, Bundesländer etc.). Um den Download und den späteren Import vom Zeitaufwand gering zu halten, laden wir im Rahmen dieses Tutorials lediglich Rheinland-Pfalz im Format ". osm.pbf" herunter. Die heruntergeladene Datei sollte also den Namen "rheinland-pfalz-latest. osm. pbf" tragen.

Import

Nun, wo wir unsere Kartendaten haben, stellt sich noch die Frage, wie wir diese in unsere PostgresDB importiert bekommen. Wir haben hierbei gute Erfahrungen mit dem Tool osm2po gemacht. Die Installation von osm2po ist schnell erledigt:

  1. Herunterladen
  2. In gewünschtem Verzeichnis ablegen
  3. Entpacken

Damit osm2po funktioniert, benötigen Sie die Java Runtime Environment (JRE) Version 8 oder höher. Navigieren Sie nun in der Kommandozeile in das Installationsverzeichnis von osm2po und führen Sie den folgenden Befehl aus (PATH_TO_PBF bitte durch den Pfad zur vorhin heruntergeladenen pbf-File ersetzen):

Hierdurch werden zwei SQL-Insert-Skripte im Unterordner rlp erzeugt (eines für die Knoten und eines für die Kanten). Diese müssen wir jetzt noch auf unserer Datenbank ausführen. Hierzu können Sie beispielsweise das Kommandozeilen-Tool psql verwenden (HOST, PORT und USERNAME bitte durch ihre eigene Konfiguration ersetzen):


Wenn alles geklappt hat, sollten sie in ihrer Datenbank die beiden Tabellen r1p_2po_4pgr (Kanten) und "r1p_2po_vertex" (Knoten) vorfinden. Herzlichen Glückwunsch, der schwierigste Teil liegt jetzt hinter uns!

Berechnung von Routen

Also gut, unsere PostgresDB steht, pgRouting ist einsatzbereit und zu guter Letzt haben wir auch noch OSM-Daten für Rheinland-Pfalz in unsere Datenbank importiert. Kurzum: Das eigentliche Vergnügen kann jetzt beginnen.

Unsere erste Route

Wir möchten also unsere erste Route berechnen. Hierfür stellt pgRouting eine Reihe von Funktionen bereit, die sich im gewählten Algorithmus (Dijkstra, A-Star etc.), der Direktionalität (unidirektional vs. bidirektional) und der Anzahl der Start- bzw. Zielknoten (One-to-One, One-to-Many etc.) unterscheiden. Wer mehr zu den verschiedenen Varianten und den jeweiligen Vor- und Nachteilen wissen will, sei auf die pgRouting-Dokumentation verwiesen.

Wir verwenden im Folgenden einfach den unidirektionalen Dijkstra, welcher mit pgr aufgerufen wird. Kommen wir also zu unserer ersten Routenberechnung. Führen Sie dazu folgende Query aus:


Das Ergebnis sollte dann so aussehen:

Wir haben also eine Route vom Knoten mit der id=l zum Knoten mit der id=100 berechnet. Das Ergebnis ist eine Tabelle, die uns im Wesentlichen darüber informiert, welche Knoten man auf diesem Weg nacheinander abläuft (siehe Spalte "node"). Nun sind an diesem Ergebnis drei Dinge nicht
zufriedenstellend:
  1. Die Eingabe: Es ist nicht gerade zweckmäßig, pgRouting die Ids der Knoten mitzuteilen, zwischen denen man eine Route berechnen Es wäre intuitiver, einfach Start- und Zielkoordinaten in Längen- und Breitengrad anzugeben.
  2. Die Ausgabe: Es wäre (analog zur Eingabe) praktischer, nicht die Ids sondern die Koordinaten der Knoten der berechneten Route zu erhalten.
  3. Die Darstellung: Das Ergebnis einer Routenberechnung macht in Tabellenform nicht gerade viel her. Schöner wäre es, die berechnete Route auf einer Karte zu visualisieren.
Um die ersten beiden Punkte kümmern wir uns in den nächsten beiden Teilkapiteln. Mit der Darstellung
setzen wir uns dann später auseinander.

Optimierung der Eingabe

Um statt Knoten-Ids die Längen- und Breitengrade der Start- und Zielkoordinaten zu Übergeben, verwenden wir folgende Query:
Zunächst wandeln wir für die Startkoordinate das Tuple (Längengrad, Breitengrad) mit der PostGis-
Funktion ST_MakePoint(...) in ein Geometrie-Objekt um. Mithilfe des Abstandsoperators < - > können
wir nun die Knoten anhand ihres Abstands zum diesem Objekt (unserem Startpunkt) sortieren. Die Id des Knotens mit dem geringsten Abstand zur Startkoordinate speichern wir in der Variable "start". Für die Zielkoordinate verfahren wir analog. Die ermittelten Knoten-Ids können wir dann an die Funktion
pgr_dijkstrsa(...) übergeben.

💡 Sie kennen die Längen- und Breitengrade, der von Ihnen gewünschten Start- und Zielorte, nicht? Kein Problem, mit Tools wie Google Maps oder bboxfinder lassen sich diese leicht herausfinden. Im Falle von Google Maps etwa reicht ein Rechtsklick auf die Karte.

Optimierung der Ausgabe

Analog zur Eingabe möchten wir nun dafür sorgen, dass wir auch beim Ergebnis nicht einfach nur Knoten-Ids, sondern auch die zugehörigen Längen- und Breitengrade erhalten. Betrachten wir dazu folgende Query:
Diese Query hat große Ähnlichkeiten zu unserer vorherigen. Sowohl die Bestimmung der Start- und
Endknoten als auch die Verwendung der Funktion pgr_dijkstrsa(...) sind identisch. Zusätzlich joinen
wir aber nun noch die Tabelle mit den Knoten (rlp_2po_vertex) an die bisherige Ergebnis-Tabelle dran. Mit Hilfe der Funktionen ST_X(...) und ST_Y(...) können wir aus der Knoten-Geometrie (geom_vertex) Längen- und Breitengrade der Knoten bestimmen. Die Ausgabe hat nun übrigens folgende Form:
💡 Bei Bedarf kann die SELECT-Klausel natürlich dahingehend angepasst werden, sich mehr Informationen als nur die Längen- und Breitengrade zurückgeben zu lassen. Für unsere weiteren Zwecke, also die Visualisierung der Route, benötigen wir aber nicht mehr.

Visualisierung der Route

Die Visualisierung der Route erledigen wir in der Programmiersprache R mithilfe des Leaflet-Packages.
Zunächst laden wir die benötigten Bibliotheken:
  • library(DBI)
  • library(odbc)
  • library(leaflet)
Dann stellen wir eine Verbindung mit unserer PostgresDB her und senden unsere Query zur
Routenberechnung ab. Das Ergebnis speichern wir dann in der Variable route:
Zu guter Letzt kommen wir zur Visualisierung der Route. Hierzu müssen wir im Wesentlichen einfach die lat- und long-Spalte an die Funktion addpolylines(...) von leaflet übergeben:

Die Ausgabe sollte dann wie folgt aussehen:

Recap

Fassen wir also nochmal zusammen. Wir haben ...
  • eine Datenbank angelegt und auf dieser pgRouting aktiviert,
  • mithilfe von osm2po OSM-Daten in unsere Datenbank importiert,
  • den Dijkstra-Algorithmus genutzt, um eine Route zwischen zwei Koordinaten zu berechnen 
  • und diese Route in Leaflet "visualisiert.
MJir hoffen dieses Tutorial konnte den Einstieg in pgRouting erleichtern und einen ersten Einblick in die, durch dieses Tool entstehenden, Möglichkeiten geben. Nun liegt es an Ihnen, sich auf dieser Grundlage weiterzubilden. Hierbei wünschen wir viel Erfolg!

Transparenzhinweis

Diese Seite wurden von mir nach dem Hackerangriff auf unsere Hochschule aus einem von Bastian gespeicherten PDF rekonstruiert und hier im im Blog dokumentiert. 
Mann war das ein Aufwand 😏.


Blog: , Seite:
Version: 1.3 Mai 2023, Kontakt: E-Mail Martin Wölker
Pirmasens, Germany, 2018-2024, ausgelesen am: , Licence CC BY-NC-SA




Kommentare

Kommentar veröffentlichen