pgRouting - Eine Einführung

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 Vorausssetzungen, die erfüllt sein müssen, bevor man mit diesem Tutorial beginnt. Folgende Tools müssen bereits installiert sein:

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

Noch ein paar Anmerkungen hierzu:

• Sollte die Installation von pgRouting Schwierigkeiten bereiten, so kann man in Windows auch auf den Application Stack Builder zurückgreifen. 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 EXTENSION 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 OpenStreetMap (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):

java -Xmx24g -jar osm2po-core-5.5.5-signed.jar prefix=rlp cmd=tjsp tileSize=x PATH_TO_PBF postp.0.class=de.cm.osm2po.plugins.postp.PgRoutingWriter postp.1.class=de.cm.osm2po.plugins.postp.PgVertexWriter

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):

psql --host HOST --port PORT --username USERNAME --password --dbname routing_db --file rlp/rlp_2po_4pgr.sql

psql --host HOST --port PORT --username USERNAME --password --dbname routing_db --file rlp/rlp_2po_vertex.sql

Wenn alles geklappt hat, sollten sie in ihrer Datenbank die beiden Tabellen rlp_2po_4pgr (Kanten) und rlp_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_dijkstra(...) aufgerufen wird. Kommen wir also zu unserer ersten Routenberechnung. Führen Sie dazu folgende Query aus:

SELECT *
FROM
	pgr_dijkstra(
		'SELECT id, source, target, cost, reverse_cost FROM rlp_2po_4pgr',
		1,
		100
	)
;

Das Ergebnis sollte von folgender Form sein:

Wir haben also eine Route vom Knoten mit der id=1 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 will. 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:

-- Find nearest node to start coordinate
WITH start as (
  SELECT id
	from rlp_2po_vertex
	order by geom_vertex <-> ST_SetSRID(ST_MakePoint(7.361226,49.260250), 4326)
	limit 1
),

-- Find nearest node to end coordinate
destination as (
	SELECT id
	from rlp_2po_vertex
	order by geom_vertex <-> ST_SetSRID(ST_MakePoint(7.601788,49.210645), 4326)
	limit 1
)

-- Calculate the route
SELECT *
FROM pgr_dijkstra('
SELECT id,
	  source,
	  target,
	  cost,
	  reverse_cost
FROM rlp_2po_4pgr',
array(SELECT id FROM start),
array(SELECT id FROM destination),
TRUE) as route
;

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_dijkstra(...) übergeben.

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:

... // Lines omitted


-- Calculate the route
SELECT
	ST_X(geom_vertex) as long,
	ST_Y(geom_vertex) as lat
FROM
	pgr_dijkstra('
	SELECT id,
		  source,
		  target,
		  cost,
		  reverse_cost
	FROM rlp_2po_4pgr',
	array(SELECT id FROM start),
	array(SELECT id FROM destination),
	TRUE) as route
	
	INNER JOIN
	
	rlp_2po_vertex as nodes
	
	ON route.node = nodes.id
;

Diese Query hat große Ähnlichkeiten zu unserer vorherigen. Sowohl die Bestimmung der Start- und Endknoten als auch die Verwendung der Funktion pgr_dijkstra(...) sind identisch. Zusätzlich joinen wir aber nun noch die Tabelle mit den Knoten (rlp_2po_vertex) an die bisherige Ergebnis-Tabelle dran. Mithilfe 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:

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:

con_to_routing_db <- DBI::dbConnect(odbc::odbc(),
                      Driver   = "Fill in your driver",
                      Server   = "Fill in your host",
                      Database = "Fill in your database name",
                      UID      = "Fill in your user name",
                      PWD      = "Fill in your password",
                      Port     = "Fill in your port")

query <- "
         ... // Lines omitted (just fill in query from above)
         "
route <- dbGetQuery(conn = con_to_routing_db, statement = query)
dbDisconnect(con_to_routing_db)

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:

leaflet(width = "100%",
        height = "100vh") %>% 
  addTiles() %>% 
  addPolylines(lat = route$lat,
               lng = route$long)

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.

Wir 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!