Routing mit PostGIS
Einführung in PostGis und pgrouting
Die Seite gibt eine Enführung in das Arbeiten mit PostGIS und behandelt die Kürzeste-Wege-Suche mit pgrouting
Inhaltsverzeichnis
-
Routing mit PostGIS
- Einführung in PostGis und pgrouting
- Verfasser
- Ausgangssituation / Problemstellung
- Aufsetzen der Arbeitsumgebung unter Windows
- Aufsetzen der Arbeitsumgebung unter Linux
- Arbeiten mit PostgreSQL – das pgAdmin Tool
- Aufsetzen der Visualisierungssoftware QGIS und Anbindung an die Datenbank
- Import von OSM Daten in die Datenbank
- Aufbereitung von OSM Daten für Routing / Erzeugen der Basis-Topologie
- Anhang
Verfasser
- Kurt Weninger
Ausgangssituation / Problemstellung
Evaluiert werden soll die Ermittlung der Kürzesten Wege Matrix für ausgewählte Standorte in Österreich basierend auf den Straßendaten des OpenStreetMap Projektes (http://www.openstreetmap.org/) mit Hilfe von Open Source Software. Die Vorgabe war die Lösung der Aufgabenstellung mit Hilfe von PostGIS (http://postgis.refractions.net/), einer Erweiterung der bekannten Datenbanksoftware PostgreSQL (http://www.postgresql.org/) um „graphische" Funktionen. Die Lösung wurde vorgeschlagen da insbesondere für große Datenmengen eine zugrunde liegende Datenbank, welche genau darauf ausgelegt ist, als geeignet erscheint. Für die notwendigen Berechnungen der Kürzesten Wege Matrix wird außerdem noch eine zusätzliche Erweiterung in Form der pgRouting (http://www.pgrouting.org/) Library eingesetzt, welche optimierte Algorithmen zur Verfügung stellt. Zusätzlich sollen die Daten auch mit Hilfe von Open Source GIS Software visualisiert werden. Hierfür wird QuantumGIS (QGIS (http://www.qgis.org/)) gewählt. Die notwendigen Schritte im Rahmen dieser Aufgabe sind:
- Einrichtung der Arbeitsumgebung (Installation und Konfiguration von PostgreSQL, PostGIS, pgRouting und QGIS)
Aufbereitung der Rohdaten (Straßendaten von OpenStreetMap (im Folgenden OSM abgekürzt), sowie die Quell- und Zielstandorte) für die Verarbeitung mit PostGIS
- Einbindung der PostGIS Daten in das Visualisierungstool QGIS
- Aufbereitung der OSM Daten für die Berechnung von Kürzesten Wegen (Erstellung eines Topologie-Graphen)
- Anbindung der Quell- und Zielstandorte an den Topologie-Graphen
- Ermittlung der kürzesten Wege Matrix für ausgewählte Standorte
- Ermittlung der zu erwartenden Zeit für die Berechnung der kompletten KW-Matrix
- Berechnung der gesamten KW-Matrix
Aufsetzen der Arbeitsumgebung unter Windows
Schritt 1: Installation von Postgres
Download und Ausführen des PostgreSQL Installers von http://www.postgresql.org/download/windows
Die zusätzliche Library pgRouting unterstützt zur Zeit nur PostgreSQL 8.4, daher wurde diese Version gewählt. PostGIS 2.0 befindet sich im experimentellen Bereich der Windows-Downloads. Benutzt wird daher PostGIS 1.5.2. Weiters unterstützt PostGIS noch keine 64 Bit Version von PostgreSQL, daher wird die 32 Bit Variante benutzt.
Im Zuge der Installation wurde mit dem Standard User „postgres" gearbeitet, auf die Einrichtung eines speziellen Accounts oder Datenbank-Schemas wurde verzichtet. Das hier vergebene Passwort wird dann für alle späteren Abfragen benötigt. Der Standard-Port lautet 5432. (Bei der Installation wurden alle Standardvorgaben übernommen)
Schritt 2: Installation der PostGIS Erweiterung
Nach Abschluss der Installation von PostgreSQL kann mit Hilfe des enthaltenen Application Stack Builder die PostGIS Erweiterung 1.5.2 nachinstalliert werden.
Benutzer: postgres
Passwort: [passwort] (Das vergebene Passwort)
Port: 5432
Falls nach einem Download-Mirror gefragt wird -> beliebige Auswahl, danach die Default Auswahl übernehmen und wenn gefragt das Passwort eingeben. Die erzeugte Template-Datenbank könnte man z.B. postgis-template nennen.
Die Frage, ob man den shp2psql graphical loader plugin enablen möchte wird ebenfalls mit JA beantwortet. Damit lassen sich später .shp Files einfach in die Datenbank importieren.
Schritt 3: Erzeugen der Arbeitsdatenbank
Dies kann mit dem pgAdmin Tool gemacht werden (siehe Kap. 4 weiter unten)
Schritt 4: Aufsetzen von pgRouting
pgRouting kann von http://www.pgrouting.org/download.html heruntergeladen werden. Für Windows ist das http://www.wiesenhaan.com/pgrouting/pgRouting-1.03_pg-8.4.2.zip. Die Datei muss in ein Verzeichnis entpackt werden. Im entpackten Verzeichnis befinden sich nun 3 Unterverzeichnisse. Doc enthält die Dokumentation und muss für die Installation nicht weiter beachtet werden. Im Lib Verzeichnis befinden sich 3 *.dll Dateien. Diese müssen in das lib Verzeichnis der PostgreSQL Installation kopiert werden (standardmäßig: C:\Program Files (x86)\PostgreSQL\8.4\lib). Mit den *.sql File des Ordners Share\Contrib müssen die entsprechenden SQL-Funktionen in die Datenbank geladen werden. Dies sollte auf der zuvor erzeugten Arbeitsdatenbank (z.B. testgis) gemacht werden. Dazu eine Command-Shell öffnen und zu den *.sql Dateien von pgRouting navigieren.
Durch Ausführen der Befehle
werden die SQL Funktionen in der Datenbank erzeugt.
Anmerkung: Die erweiterten Funktionen sind komischerweise im Standardpaket nicht enthalten. Diese müssen manuell von https://github.com/pgRouting/pgrouting/tree/master/extra/driving_distance/sql
heruntergeladen werden.
Aufsetzen der Arbeitsumgebung unter Linux
Als Basis wurde Ubuntu 11.04 genommen, das in einer VirtualBox läuft. Virtualbox Version war 4.1.0 r73009 (Windows Version). Das Ubuntu Image wurde fertig von http://virtualboxes.org/images/ubuntu/ geladen (Ganz genau http://sourceforge.net/projects/virtualboximage/files/Ubuntu%20Linux/11.04/ubuntu_11.04-x86.7z/download) . Anmerkung: Für die Arbeit mit größeren Datenmengen ist eine größere Festplatte sinnvoll. Das kann aber auch später durch Erzeugen einer neuen größeren Virtual Disk und Verlagern der Ubuntu Installation nachgeholt werden. (Insbesondere die Funktion ST_DWithin sorgt für einen großen Bedarf an Festplattenspeicherplatz umso größer der Radius angegeben wird.) Alle Befehle müssen im Terminal eingegeben werden. Password des Users ubuntu ist „reverse".
Installation von Postgres
1 sudo apt-get install postgresql-8.4 postgresql-client-8.4 postgresql-contrib-8.4 pgadmin3
2 sudo apt-get install postgres-server-dev-8.4
(auf manchen Systemen auch sudo apt-get install postgres-server-dev-all)
Installation von PostGIS
1 sudo apt-get install postgresql-8.4-postgis
Erzeugen der PostGIS template database
(Das geht unter Linux nicht automatisch, so wie bei der Windows Installation.)
Test, ob es geklappt hat (noch als User postgres):
1 psql –d postgistemplate –c „SELECT postgis_full_version();
Als Ergebnis wird die Versionsnummer von PostGIS angezeigt (hier 1.5.1)
Unter Linux muss zusätzlich noch das postgres Passwort gesetzt werden (sonst fuktioniert pgAdmin nicht):
1 sudo su postgres -c psql template1
In der Datenbank wird nun das Passwort geändert:
1 template1=# ALTER USER postgres WITH PASSWORD ‘password’;
2 template1=# \q
3
Das ändert das Passwort der Datenbank, jetzt muss auch noch das Passwort des Accounts auf das gleiche Passwort geändert werden.
1 sudo passwd –d postgres
2 sudo su postgres –c passwd
Bei der Nachfrage das gleiche Passwort eingeben. Ab jetzt funktioniert der pgAdmin und die Arbeitsdatenbank kann erzeugt werden (gleich wie unter Windows) – siehe nächstes Kapitel.
Einbinden der pgRouting Library
1 sudo apt-get install build-essential git-core cmake
2 sudo apt-get install libboost-graph-dev
3 sudo apt-get install libcgal*
4
5 wget http://sourceforge.net/projects/gaul/files/gaul-devel/0.1850-0/gaul-devel-0.1850-0.tar.gz
6 tar -zxvf gaul-devel-0.1850-0.tar.gz
7 cd gaul-devel-0.1850-0
8 ./configure --disable-slang
9 make
10 sudo make install
11 sudo ldconfig
12
13 git clone git://github.com/pgRouting/pgrouting.git pgrouting
14 cd pgrouting/
15 cmake -DWITH_TSP=ON -DWITH_DD=ON .
16 make
17 sudo make install
Bei Problemen mit Compiler-Pfaden -> prüfe ob sudo apt-get install postgres-server-dev-8.4 fehlt
Als letzter Schritt muss nun die Datenbank mit den neuen Funktionen ausgestattet werden.
1 psql -U postgres –d postgis -f /usr/share/pgrouting/routing_core.sql
2 psql -U postgres –d postgis –f /usr/share/pgrouting/routing_core_wrappers.sql
3 psql -U postgres –d postgis -f /usr/share/pgrouting/routing_topology.sql
TSP functions
1 psql -U postgres –d postgis -f /usr/share/pgrouting/routing_tsp.sql
2 psql -U postgres –d postgis -f /usr/share/pgrouting/routing_tsp_wrappers.sql
Driving Distance functions
1 psql -U postgres –d postgis -f /usr/share/pgrouting/routing_dd.sql
2 psql -U postgres –d postgis -f /usr/share/pgrouting /routing_dd_wrappers.sql
Falls man mit Entwicklerbranches arbeiten möchte (siehe https://github.com/pgRouting/pgrouting https://github.com/pgRouting/pgrouting), kann man mit
1 git clone -b <branch> <remote_repo>
einen Branch laden.
Bsp.:
1 git clone –b gsoc-tdsp git://github.com/pgRouting/pgrouting.git pgrouting_gsoc
Neuere Branches benutzen oft die CUnit Tests. Dann muss für erfolgreiches Compilieren auch noch
1 sudo apt-get libcunit1 libcunit1-dev libcunit1-doc
ausgeführt werden
Arbeiten mit PostgreSQL – das pgAdmin Tool
Das Tool ist unter Windows und Linux vorhanden und gleich zu bedienen.
Einstieg
Start des pgAdmin Tools
Aufruf der „Add Server" Funktion im „File" Menü und Ausfüllen der Felder Name, Host, Username und Passwort mit den Einstellungen, die bei der Installation vorgenommen wurden. (Host ist „localhost", wenn der Server am selben rechner läuft)
Erzeugen einer Arbeitsdatenbank basierend auf der PostGIS-erweiterten Template-Datenbank
Aufruf des Dialog (ReM auf Database)
Eingabe des Namens und der Template Datenbank ist ausreichend.
Auf OK klicken die Datenbank wird erzeugt.
Achtung: Es darf keine Verbindung zur Template Datenbank bestehen, sonst wird die Erstellung verweigert. („Keine Verbindung" wird angezeigt durch das rote x)
Import von *.shp Dateien mit dem shp2psql GUI Plugin
Auswahl des *.shp Files mit dem FileDialog (oben). Falls bekannt, sollte die korrekte SRID gesetzt werden. Wenn es beim Import Probleme gibt, ist manchmal das Encoding ein Problem. In diesem Fall muss der „Options" Dialog geöffnet werden.
und das Encoding geändert werden. In der aktuellen Auswertung war es notwendig auf „LATIN1" zu ändern.
Aufsetzen der Visualisierungssoftware QGIS und Anbindung an die Datenbank
Windows Installation
Unter Windows wird der Installer ( http://qgis.org/downloads/QGIS-OSGeo4W-1.7.0-b55a00e73-Setup.exe) heruntergeladen und installiert. Unter Linux muss das Repository erst zu den Quellen hinzugefügt werden.
Linux Installation
Dazu müssen zuerst die Quellen für den Paket-Manager hinzugefügt (Ohne das geht es auch, dann wird aber QGIS 1.4 installiert, aktuell zum jetzigen Zeitpunkt ist aber 1.7) werden. Editieren der Datei /etc/apt/sources.list (z.B. mit gedit ).
1 sudo gedit /etc/apt/sources.list
Hinzufügen von
1 deb http://qgis.org/debian natty main
2 deb-src http://qgis.org/debian natty main
Speichern, dann die Paketinformationen updaten mit
1 sudo apt-get update
und qgis installieren.
1 sudo apt-get install qgis
Unter Windows befindet sich QGIS unter 'Start|Programme|Quantum GIS Wroclav, in Linux unter Application|Science
Anbindung an die PostGIS-Datenbank
(Voraussetzung ist, das der darzustellende Table eine dedizierte Geometry-Spalte aufweist. Zu prüfen ist das in PostgreSQL für den Table myTable mittels SELECT * FROM geometry_columns WHERE f_table_name = ‘myTable’; Der resultierende Eintrag zeigt dann die Parameter der Geometry Spalte. (Siehe http://postgis.refractions.net/docs/ch04.html#RefObject für Details)
Hinzufügen eines PostGIS Layers
Hinzufügen einer neuen Datenbankverbindung
Eintragen der Postgres Verbindungsdaten. Benutzername, Passwort, Port und Datenbank
Klickt man nun auf „Verbinden", werden die Tabellen angezeigt, die eine geometry Spalte besitzen.
Die gewünschten Tabellen können gewählt und durch Drücken des Buttons „Hinzufügen" dem Projekt hinzugefügt werden (Mit dem Befehl „Abfrage erstellen“ können auch spezielle SQL Queries ausgeführt werden.) . Als Ergebnis erhält man z.B.:
(Die Daten stammen aus der Übung Methoden der Regionalanalyse und Standortbewertung
Import von OSM Daten in die Datenbank
Import der Daten mit osm2pqsql
(Dieser Schritt muss zur Durchführung der KW-Matrix Berechnung nicht durchgeführt werden, wird aber der Vollständigkeit halber angeführt.)
OSM Daten können z.B. von http://download.geofabrik.de/osm/europe/ http://download.geofabrik.de/osm/europe/ heruntergeladen werden.
[Anm. Will man z.B. zu Testzwecken nur einen Teilausschnitt der Map, kann man die entsprechen-den Daten aus dem OSM File extrahieren (vgl. hierzu http://wiki.openstreetmap.org/wiki/Osmosis#Extracting_bounding_boxes) .]
Vor dem Import der Daten in die Datenbank muss der Postgres hstore Support in der Datenbank eingeschaltet werden. Das erfolgt in Windows durch das Öffnen einer Command-Shell und Eingabe von
1 psql –f hstore.sql –d postgis –U postgres
(hstore.sql muss im Pfad liegen, sonst muss der komplette Pfad angeben werden. Die Datei hstore.sql liegt im PostgreSQL-Installationsverzeichnis unter \share\contrib)
Nun kann das Tool osm2psql von http://wiki.openstreetmap.org/wiki/Osm2pgsql#Windows_XP heruntergeladen werden. Die Datei muss nicht installiert, sondern nur entpackt werden.
Nächster Schritt ist das Öffnen einer Command-Shell und Wechsel ins Verzeichnis mit den zuvor entpackten Daten. Mit dem Befehl
1 osm2pgsql -d postgis –U postgres –S default.style –-hstore mapfile.osm.bz2
können nun die OSM Daten in die gewählte Datenbank importiert werden. Im Falle einer Passwortabfrage wird das Passwort der Datenbank eingegeben.
-d Datenbank
-U Benutzer
In der Datenbank befinden sich anschließend die folgenden Tabellen (Darstellung ist ein Auszug aus http://wiki.openstreetmap.org/wiki/Osm2pgsql/schema) :
planet_osm_line: contains all imported ways
planet_osm_point: contains all imported nodes with tags
planet_osm_polygon: contains all imported polygons. Relations seem to be resolved for that.
planet_osm_roads: contains a subset of planet_osm_line suitable for rendering at low zoom levels.
Alternativ lassen sich *.shp Daten mit dem SPIT Plugin von QGIS sehr komfortabel in die Datenbank importieren:
Zunächst muss die SPIT Erweiterung aktiviert werden. Das geht in der Plugin-Verwaltung
Danach steht das Menü unter „Erweiterungen" zur Verfügung:
Im SPIT Menü muss dazu eine Verbindung zur Datenbank erzeugt werden. Die Daten sind hier dann die gleichen wie oben (Verbunden werden soll zur Arbeitsdatenbank z.B. postgis)
Beim Import kann alles auf Standardeinstellung gelassen werden, nur die SRID kann eingegeben werden, wenn die Projektion bekannt ist. Das kann aber auch später in PostGIS erfolgen, indem die geometry_column adaptiert wird.
Aufbereitung von OSM Daten für Routing / Erzeugen der Basis-Topologie
Für die Erzeugung des Topologie-Graphen aus den OSM Daten wurde das Tool osm2po benutzt, das von http://osm2po.de/ http://osm2po.de/ heruntergeladen werden kann. Benutzt wurde die Version 4.1.6, aktuell steht die Version 4.1.9 zur Verfügung. Das Tool ist Java-basiert, analysiert das OSM File und generiert eine SQL-Datei, die in die Datenbank importiert werden kann. Auch hier ist keine Installation notwendig, das Tool muss nur in ein Verzeichnis entpackt werden. Eine entsprechende JAVA JRE Installation wird als gegeben (weil üblicherweise vorhanden) angesehen.
Im Verzeichnis, das die entpackten Daten beinhaltet, wird eine Command-Shell geöffnet.
Der Aufruf des Tools lautet
1 java -jar osm2po-core-4.1.6-signed.jar prefix=pref mapfile.osm.bz2
Erzeugt wird ein Unterverzeichnis mit dem Namen pref, in diesem befindet sich die SQL Datei pref_2po_4pgr.sql, mit welcher die Daten in die Datenbank importiert werden können. Die Syntax hierfür lautet:
1 psql –q -f pref_2po_4pgr.sql –d postgis -U postgres
-d Datenbank
-U Benutzer
Als Ergebnis befindet sich nun eine Tabelle mit Namen pref_2po_4pgr in der Datenbank, welche den Topologie-Graphen enthält.
Anmerkung: Die Erstellung des Topologie-Graphen kann durch Ändern der Tool-Konfiguration mittels Änderung der Paramater in der Datei osm2po.config beeinflusst werden. Höchstgeschwindig-keiten der jeweiligen Straßentypen und Befahr- sowie Begehbarkeiten können festgelegt werden (Hier muss man durch Auswahl einer kleineren OSM Map und ausprobieren die beste Variante finden.) .
Die Kosten einer Kante werden als Zeitaufwand in Stunden in Abhängigkeit von Länge der Kante und erlaubter Höchstgeschwindigkeit berechnet.
Ausgangspunkt der weiteren Arbeit sind die OSM Daten für Österreich, die mit osm2po (siehe Kap.7) in einen routingfähigen Graphen umgewandelt wurden. Das resultierenden SQL File wurde in die Datenbank geladen. Im nächsten Schritt wurden zunächst die Wohnstandorte in QGIS geladen. Dort wurde der KBS auf die korrekte (alte) MGI/Lambert Projektion umgestellt und danach der Layer mit korrigiertem neuen MGI/Lambert (SRID 31287) exportiert. Selbiges mit den Zielen. Das war der schnellste und einfachste Weg. Danach wurden die Daten über das shp2psql GUI in die Datenbank geladen (unter Linux geht es auch mit dem QGIS SPIT-Plugin sehr gut). Damit sind die notwendigen Ausgangsdaten für die Kürzeste Wege Berechnung vollständig. In der Datenbank werden die Wohnstandorte und Zielstandorte in einer Tabelle Standorte vereinigt, für welche dann anschließend die Anbindung an den bestehenden Graphen erfolgt.
Anbindung der Standorte an den Topologie-Graphen
Mit der PostGIS Funktion ST_ShortestLine wurde der kürzeste Abstand zur nächstgelegenen Strasse ermittelt. Dafür werden alle in einem bestimmten Umkreis gelegenen Strassen genommen, der Abstand zur jeweiligen Straße berechnet, die Abstände für jeden Standort der Größe nach geordnet und der kleinste Abstand als der richtige genommen und in die Verbindungstabelle eingefügt.
Der zugehörige SQL Befehl sieht dann so aus:
1 CREATE TABLE conns AS
2 SELECT DISTINCT ON (po.gid) po.gid AS pt_osm_id, st.osm_id AS st_osm_id, po.the_geom AS pt_way, ST_Transform(st.geom_way,31287) AS st_way, ST_ShortestLine(po.the_geom,ST_Transform(st.geom_way,31287)) AS con, ST_Length(ST_ShortestLine(po.the_geom, ST_Transform(st.geom_way,31287))) AS len, st.*
3 FROM standorte AS po INNER JOIN rout_test AS st ON ST_DWithin(po.the_geom, ST_Transform(st.geom_way,31287),2000) ORDER BY po.gid,len;
Je nach Anzahl von Kanten im Topologie-Graphen, Anzahl von Standorten und Umkreis der genommen wird, dauert dieser Vorgang länger und benötigt unterschiedlich viel Speicher. (im worst case ist das eine O(m*n) Operation, auf jeden Fall muss ein spatial Index benutzt werden.
(z.B. 1035 Standorte mit einem Umkreis von 500 m benötigen ca. 20 Sekunden, mit einem Abstand von 2000m schon mehr als 70 Sekunden)
Im nächsten Schritt werden die Standorte mit Hilfskanten in den Topologie-Graphen eingefügt. Dazu wird von jedem Standort-Knoten eine Kante zum linken und eine zum rechten Endpunkt der nächstliegenden Linie eingefügt. (liegt der Standort-Knoten am nächsten zu einem der Enpunkte, dann nur eine zum jeweiligen Endpunkt).
Bildlich kann man sich das so vorstellen:
Die Hilfs-Kanten L1 und L2 werden eingefügt und erhalten das anteilig das Gewicht des Teilstücks der originalen Kante. Dadurch kann jetzt vom Punkt n+1 geroutet werden, als ob er sich auf der Kante befinden würde. Der Vorteil ist hier, dass der originale Topologie-Graph nicht aufgebrochen, sondern nur erweitert wird. Im entstandenen Graphen kann nun die Berechnung der kürzesten Wege durchgeführt werden. Benutzt wird dazu die Funktion driving_distance, die in der Driving-Distance Erweiterung der pgRouting Library enthalten ist. Die Funktion berechnet die kürzesten Wege eines Knotens zu allen anderen Knoten in einem Aufruf.
1 SELECT m_source,vertex_id,cost FROM driving_distance(
2 ‘SELECT id AS id,source,target, cost, reverse_cost
3 FROM rout_test’,m_source ,10000000,false,true) AS foo
4 WHERE foo.vertex_id > offset;
m_source ist die ID des Ausgangsknotens. Der Wert 10000000 steht für die Abbruchbedingung der maximal zulässigen Kosten (hier aus Testzwecken quasi ∞). Der Topologie-Graph hat enthält auch reverse costs, die vom Algorithmus berücksichtigt werden. In der SQL Funktion calc_kv_table() wird dies für alle Wohnstandorte durchgeführt und eine Tabelle erzeugt.
Zur Standortanbindung:
Eine kurze Analyse der Standortanbindung an der Untersuchung der Anbindung der 1035 Wohnstandorte an den aufbereiteten Straßengraphen von Österreich unter Variierung des betrachteten Umgebungspuffers zeigt folgendes Ergebnis (Die Messung wurde unter Windows mit einmaligem Durchlauf durchgeführt. Die absoluten Zahlen werden daher variieren, es zeigt sich jedoch der Trend.):
Die meisten Standorte befinden sich in einer sehr nahen Umgebung des Straßennetzes. Bereits in einem Radius von 200 Metern werden 98% der Standorte angebunden. Um mit einer allgemeinen Funktion wirklich alle Standorte anbinden zu können, muss der Radius auf 2000 (Für die kompletten Daten ist noch eine Erweiterung des Radius nötig, da 1895 Standorte mehr als 2000m von befahrbaren Straßen entfernt liegen .) Meter erweitert werden, was die Dauer mehr als verfünffacht. Man sieht den Verlauf auch im Diagramm:
Die notwendige Optimierung liegt hier in einer stufenweisen Durchführung mit verschiedenen immer größer werdenden Radien. Man startet mit einem Radius von 50 Metern und führt die Anbindung durch. Für die dann noch nicht angebundenen Standorte wird die Anbindung mit einem Radius von 200 Metern wiederholt und danach eine Anbindung der restlichen Punkte mit einem Radius von 2000m. Unter der Annahme, dass die Anbindung (egal ob erfolgreich oder nicht) pro Punkt genau gleich lang dauert (innerhalb einer Distanzstufe), würde sich die Dauer der Anbindung mit der vorgeschlagenen Methode in 15,6 Sekunden bei Anbindung aller Punkte durchführen lassen (Die zusätzlichen Kosten für die Aussortierung der schon angebundenen Punkte werden hier vernachlässigt.) .
Ein Test der Methode auf drei Anbindungsvorgänge mit 50, 200 und 2000m ergibt eine Dauer von ca. 38 Sekunden. Das ist beträchtlich mehr als die angenommene Verbesserung auf 15,6 Sekunden, aber immer noch eine fast 50%-ige Verbesserung. Interessant ist, dass hier jede Anbindung ca. 12-13 Sekunden dauert, obwohl doch unterschiedlich viele Punkte betroffen sind. Die Kosten für das Aussortieren sind jedoch tatsächlich zu vernachlässigen (Anzumerken ist noch dass durch optimierte Verwendung des Spatial Index die Dauer noch beträchtlich weiter reduziert werden konnte. Es ist sehr wichtig in PostgreSQL zu kontrollieren, ob die Indices auch richtig und vollständig eingesetzt werden.) . Als Grenzwert für die Berechnung der kürzesten Wege wurden 2h angenommen.
Es hat sich jedoch gezeigt, dass bei verbesserter Wahl der Indexsetzung die Dauer noch weiter in Richtung des erwarteten Wertes gesenkt werden kann.
Hardwareausstattung des Rechners:
- Prozessor: Intel Xeon W3520 (2.67 GHz)
- Speicher: 8 GB RAM
- Festplatte: Fujitsu MBA3300RC SCSI Disk (180 GB)
- OS: Windows 7 Professional 64 Bit
Die Zeiten für die Arbeitsschritte ergeben sich nun wie folgt:
Windows:
Vorbereitung der Daten (CleanUp etc.) ~ 4 Minuten
- Anbindung der Standorte ~ 14 Minuten
- Adaptierung des Graphen ~ 23 Minuten
- Berechnung der KW-Matrix für 1035 Standorte ~ 12 Stunden
- Summe: ~ 12,5 Stunden
Linux :
Vorbereitung der Daten (CleanUp etc.) ~ 3 Minuten
- Anbindung der Standorte ~ 10 Minuten
- Adaptierung des Graphen ~ 17 Minuten
- Berechnung der KW-Matrix für 1035 Standorte ~ 90 Minuten
- Summe: ~ 2 Stunden
Die Berechnungsdauern zeigen extreme Unterschiede. Zum Test wurde nochmals eine einzelne Route unter Zuhilfenahme der Funktion EXPLAIN ANALYZE sowohl unter Windows als auch unter Linux berechnet.
Die Funktion lautet:
1 EXPLAIN ANALYZE SELECT * FROM shortest_path(‘SELECT id AS id, source,target, cost,reverse_cost FROM rout_test’,690001, 690014, false, true);
und berechnet den kürzesten Weg zwischen dem Knoten 690001 und 690014. Unter Linux ergibt sich eine Dauer von etwas über 3 Sekunden:
"Function Scan on shortest_path (cost=0.00..12.50 rows=1000 width=16) (actual time=3259.641..3259.887 rows=422 loops=1)"
"Total runtime: 3260.179 ms"
Unter Windows jedoch eine Zeit von über 38 Sekunden:
"Function Scan on shortest_path (cost=0.00..12.50 rows=1000 width=16) (actual time=38924.925..38924.946 rows=422 loops=1)"
"Total runtime: 38924.984 ms"
Eine Begründung dafür findet sich nicht. Ein Blick auf die Daten und Indices zeigt keine Unterschiede. Stichprobenartige Vergleiche der Ergebnisdaten und -tabellen zeigen ebenfalls keine Unterschiede. Lediglich die Versionen der verwendeten Libraries unterscheiden sich unter Linux und Windows. Ein weiterer Test ergab, dass die Berechnungsdauer unter Linux sich denen von Windows annäherten, wenn als Grenzwert der Distanzfunktion nicht mehr 2h, sondern ein Wert von 10000000 (Dieser Wert ist größer als der Grenzwert für „unbefahrbahre“ Routen. Das bedeutet auch, dass wirklich alle Routen berechnet werden, die im Graphen möglich sind.) angegeben wird. Dies lässt darauf schließen, dass es unter Windows ein Problem mit der verwendeten driving_distance Erweiterung zur pgRouting Library gibt. Dies bedarf aber einer näheren Untersuchung, die im Rahmen der Arbeit aus zeitlichen Gründen nicht mehr durchführbar war.
Anhang
Erzeugen einer Custom-Projektion für die Korrektur der alten MGI-Lambert Projektion
Für den Import „alter" Daten, die auf der MGI-Lambert Projektion mit 48.0 basieren, muss eine Custom KBS in QGIS eingerichtet werden und dem Layer zugewiesen werden (Notwendig für die Daten der Wohn- und Zielstandorte).
Zuerst auf den Stern klicken (zum Löschen), dann Daten eingeben
Name (z.B.): MGI/Lambert (48.0) Projektionsdaten: +proj=lcc +lat_1=49 +lat_2=46 +lat_0=48.0 +lon_0=13.33333333333333 +x_0=400000 +y_0=400000 +ellps=bessel +towgs84=577.326,90.129,463.919,5.137,1.474,5.297,2.4232 +units=m +no_defs Dann unbedingt speichern!! Danach kann man den Layern unter Eigenschaften das neue Koordinatensystem zuweisen um eine korrekte Darstellung zu erhalten. Sinnvollerweise wird dann das Shape-File im korrekten Koordinatensystem exportiert: Dialog kommt mit ReM auf Layer
Kodierung UTF-( (im Hinblick auf den PostGIS Import) Ziel KBS: MGI / Austria Lambert (SRID: 31287)
Quellen und Links
Information zu verwendeten OSM-Tags und Straßentypen
http://wiki.openstreetmap.org/wiki/Highway_tag_usage
http://wiki.openstreetmap.org/wiki/Tagging_samples/urban
http://wiki.openstreetmap.org/wiki/DE:Germany_roads_tagging
http://wiki.openstreetmap.org/wiki/Tag:highway%3Dliving_street
http://wiki.openstreetmap.org/wiki/DE:Tag:highway%3Dpath
http://wiki.openstreetmap.org/wiki/DE:Key:crossing
pgRouting und PostGIS Tutorials und Tipps
PostGIS http://postgis.refractions.net/docs/index.html
http://www.gis.hsr.ch/wiki/PostGIS_-_Tipps_und_Tricks
http://www.bostongis.com/downloads/pgcon2009/pgcon_spatialanal_postgis.pdf
http://www.bostongis.com/ http://www.bostongis.com/
pgRouting
http://www.davidgis.fr/documentation/pgrouting-1.02/
http://underdark.wordpress.com/2011/02/07/a-beginners-guide-to-pgrouting/
http://osm2po.de/tutorial.php http://osm2po.de/tutorial.php
https://github.com/pgRouting/pgrouting/wiki/APSP
http://wiki.openstreetmap.org/wiki/Routing
Buch
PostGIS in Action, Regina Obe and Leo Hsu, Manning Publications Co., 2011
