Dzisiaj opiszę zastosowanie pgRouting w PostgreSQL 9.2 na Windows 7 (64 bit) do wyznaczania tras w mapach OpenStreetMap. Wyznaczymy swoje trasy i stworzymy własny silnik routingu dostępny z poziomu języka SQL.
Często poszukiwaną funkcjonalnością niedostępną natywnie w PostGIS’e jest realizacja routingu czyli wyznaczania trasy pomiędzy zadanymi punktami w naszych danych przestrzennych. Problem jest szeroko rozpoznany i istnieje szereg algorytmów realizujących wyszukiwanie drogi – zależnie od potrzeb. Wbrew pozorom problem routingu nie dotyczy jedynie danych drogowych – znajduje także zastosowanie w sieciach teleinformatycznych, sieciach energetycznych a nawet w biologi i medycynie. My jednak w naszym krótkim opisie tematyki skupimy się na danych drogowych pozyskanych z projektu OpenStreetMap i przejdziemy ścieżkę od instalacji poprzez import danych aż po realizację wyszukiwarki optymalnej drogi między punktami.
Potrzebne oprogramowanie:
– PostgreSQL 9.2
– PostGIS
– pgRouting
– Dane drogowe w formacie OpenstreetMap
– Narzędzie importujące dane z formatu OSM do PostGIS’a – my wykorzystamy osm2po
Po kolei:
PostgreSQL 9.2
Do pobrania spod adresu http://get.enterprisedb.com/postgresql/postgresql-9.2.4-1-windows-x64.exe (wersja 64 bitowa) lub http://get.enterprisedb.com/postgresql/postgresql-9.2.4-1-windows.exe (wersja 32 bitowa)
Instalacja jest w miarę prosta – sprowadza się do przeklikania przez kreator. W dalszej części zakładam zainstalowanie z wykorzystaniem opcji domyślnych.
Po instalacji PostgreSQL trzeba jeszcze oczywiście zainstalować PostGIS’a (w Windows korzystając z Application Stack Buildera).
pgRouting
Biblioteka pgRouting ma oficjalną stronę internetową http://pgrouting.org niemniej w jej dziale download nie znajdziemy wersji pgRouting współpracującej z najnowszą wersją PostgreSQL. Odpowiednie binaria znaleźć możemy jednak pod adresem http://winnie.postgis.net/download/windows/pg92/buildbot/ Ja wykorzystuję na potrzeby niniejszego tutoriala http://winnie.postgis.net/download/windows/pg92/buildbot/pgrouting-pg92-binaries-2.0.0devw64.zip. Jest to wersja, która umożliwia łatwą instalację z wykorzystaniem polecenia CREATE EXTENSION
Instalacja pgRouting sprowadza się do wypakowania zawartości pobranego archiwum do katalogu PostgreSQL a następnie w bazie PostGIS’owej wywołania polecenia
CREATE EXTENSION pgrouting
Poprawność instalacji można sprawdzić przez wykonanie zapytania (powinno zwracać 1)
select count(*) from pg_proc where proname = 'shortest_path';
Dane drogowe w formacie OpenstreetMap
Ekstrakty danych dla Polski można pobrać na przykład spod adresu http://downloads.cloudmade.com/europe/eastern_europe/poland/poland.osm.bz2
Po pobraniu rozpakowujemy plik do dowolnej lokalizacji np. C:\PGIS
Narzędzie do ładowania danych OSM do bazy PostGIS – osm2po
Kiedyś najbardziej rozpowszechnionym narzędziem importującym dane OSM do PostGIS’a było osm2pgsql (http://wiki.openstreetmap.org/wiki/Osm2pgsql). Prostszym i wydajniejszym narzędziem (nie mającym problemów z dużymi zestawami danych) jest jednak osm2po (http://osm2po.de/) które nie tylko potrafi importować dane do PostGIS’a ale stanowi również samodzielny silnik routing’u z webowym interfejsem oraz serwerem aplikacji udostępniającym sieciową usługę realizującą routing w posiadanych przez nas danych (wszystko to za darmo!). Narzędzie osm2po pobieramy spod adresu http://osm2po.de/download.php?lnk=osm2po-4.7.7.zip
Instalacja sprowadza się do rozpakowania archiwum. Narzędzie wymaga zainstalowanej i działającej maszyny wirtualnej Java.
Import danych OSM do PostGIS’a
W rozpakowanym narzędziu osm2po znajdziemy plik demo.bat które stanowi przykład jak wywołać narzędzie. Aby załadować dane dla polski umieszczone w pliku C:\PGIS\osm2pgsql\poland.osm należy wywołać polecenie
java -Xmx512m -jar osm2po-core-4.7.7-signed.jar prefix=hh tileSize=x C:\PGIS\osm2pgsql\poland.osm
Chwilę to potrwa (mniej niż 3 minuty na mojej maszynie) ale w efekcie w katalogu powstanie cała seria przetworzonych plików wynikowych. Dodatkowo narzędzie osm2po uruchomi wbudowany serwer WWW który umożliwi realizację procesu routingu w oparciu o algorytmy wbudowane w narzędzie (bez PostGIS’a!). Usługa dostępna będzie pod adresem http://localhost:8888/Osm2poService Nas w kontekście tego wpisu interesuje przede wszystkim plik wynikowy wyprodukowany przez narzędzie tj. hh_2po_4pgr.sql – jest to skrypt pgsql’a ładujący dane OSM do bazy PostGIS’owej. Aby uruchomić ten plik należy wydać polecenia (oczywiście należy podać nazwę użytkownika oraz bazę danych odpowiednią do swojego środowiska):
set PGCLIENTENCODING=UTF8
psql -U [username] -d [dbname] -q -f "<ścieżka do pliku hh_2po_4pgr.sql>"
U mnie to jest:
set PGCLIENTENCODING=UTF8
psql -U postgres -d pgis -q -f "D:\Moje dokumenty\ROUTING\osm2po-4.7.7\hh\hh_2po_4pgr.sql"
Załadowanie danych chwilę potrwa ale po zakończeniu procesu w bazie danych pojawi się nowa tabele: hh_2po_4pgr w której znajdują się dane przygotowane do wykorzystania przez pgRouting. Tabela ta zawiera segmenty czyli odcinki dróg zawarte pomiędzy skrzyżowaniami. Pojedynczy segment może składać się z wielu zakrętów, ale nie ma wśród nich skrzyżowań. Z punktu widzenia routingu istotne są tylko informacje o skrzyżowaniach, ale oczywiście do wizualizacji znalezionej drogi niezbędne są całe segmenty, których współrzędne znajdziemy w kolumnie geom_way tej tabeli.
Wykorzystanie pgRouting
pgRouting wspiera następujące algorytmy wyszukania optymalnej ścieżki:
– Shortest Path Dijkstra
– Shortest Path A*
– Shortest Path Shooting Star
Pierwszy można porównać do algorytmu rysującego wypełnienie jakiegoś obszaru w Paint’e. Po kliknięciu na punkt (odpowiednik punktu startowego w routingu) kolorowane są (sprawdzane) wszystkie z nim sąsiadujące, a następie sąsiadujące z nimi (we wszystkich kierunkach) i tak aż do dotarcia do punktu docelowego. Dijkstra to szczególny przypadek A* – algorytmu mądrzejszego. Zamiast “kolorować” wszystkie sąsiadujące z już pokolorowanymi punktami koloruje te które leżą bliżej punktu docelowego (znamy przecież jego współrzędne) przez co jest dużo bardziej wydajny i szybciej kończy pracę. Ostatni z nich zwraca istotną uwagę na drogę pomiędzy punktami (z A do B może być inna niż z B do A) oraz na zakazy (restrykcje) dotyczące poruszania się po drogach (np. zakazy skrętu) i jest najbardziej odpowiedni w przypadku routingu uwzględniającego dane o ruchu drogowym.
Dla każdej z wymienionych algorytmów pgRouting udostępnia funkcję, która umożliwia realizację algorytu. Są to:
CREATE OR REPLACE FUNCTION shortest_path(
sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean)
RETURNS SETOF path_result
sql to treść zapytania SQL zwracającego listę połączeń między punktami w formacie:
id, source, target, cost
id – identyfikator krawędzi
source – identyfikator wierzchołka początkowego krawędzi
target – identyfikator wierzchołka końcowego krawędzi
cost – koszt przebycia drogi poprzez krawędź (np. czas przejazdu, długość odcinka itp.)
w przypadku ustawienia has_reverse_cost na true zapytanie powinno zwracać również piątą kolumnę zwracającą koszt z target do source
source_id to punkt startowy dla algorytmu
target_id to punkt docelowy
directed określa czy graf jest skierowany (jeśli nie jest to obecność drogi z A->B nie oznacza możliwości podróży z B->A)
has_reverse_cost – określa czy koszt podróży od końca krawędzi do początku może być inny niż zgodnie z kierunkiem krawędzi
Dla algorytmu A* nagłówek funkcji wygląda następująco:
CREATE OR REPLACE FUNCTION shortest_path_astar(
sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean)
RETURNS SETOF path_result
Zapytanie musi zwracać kolumny:
id: identyfikator krawędzi
source: identyfikator wierzchołka początkowego krawędzi
target: identyfikator wierzchołka końcowego krawędzi
cost: koszt podróży po krawędzi
x1: współrzędna x punktu początkowego
y1: współrzędna y punktu początkowego
x2: współrzędna x punktu końcowego
y2: współrzędna y punktu końcowego
reverse_cost (opcjonalny): koszt przebycia drogi w drugą stronę (od końca do początku). Na przykład dla dróg jednokierunkowych może być ujemny co oznacza zakaz przejazdu tą drogą w tą stronę. Wykorzystanie tej funkcjonalności wymaga ustawienia directed oraz has_reverse_cost na true.
Współrzędne punktów są potrzebne do tego, aby algorytm najpierw próbował dojść do punktu docelowego wybierając te leżące bliżej mety (heurystyka).
Dla algorytmu Shooting Star nagłówek funkcji wygląda następująco:
CREATE OR REPLACE FUNCTION shortest_path_shooting_star(
sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean)
RETURNS SETOF path_result
Nie będziemy się nią zajmować w tym tutorialu z uwagi na fakt, że zakazy skrętów nie są domyślnie importowane przez narzędzie osm2po.
Aby wyznaczyć najkrótszą drogę pomiędzy dwoma punktami z wykorzystaniem danych OSM można wykonać następujące zapytanie, które wyliczy drogę z Warszawy (punkt 52.231591, 20.998746) do Krakowa (50.061389, 19.938333):
select * from shortest_path(
'select id, source, target, cost, 1 as level from hh_2po_4pgr',
(select source from hh_2po_4pgr order by sqrt((x1 - 20.998746)*(x1 - 20.998746) + (y1 - 52.231591)*(y1 - 52.231591)) limit 1),
(select target from hh_2po_4pgr order by sqrt((x2 - 19.938333)*(x2 - 19.938333) + (y2 - 50.061389)*(y2 - 50.061389)) limit 1),
false,
false)
Podzapytania w wywołanu shortest_path znajdują najbliższe punktom startowym i końcowym punkty zapisane w tabeli (tylko wśród takich pgRouting będzie w stanie odnaleźć ścieżkę).
Wynik działania to trzy kolumny: vertex_id, edge_id, cost zawierające odpowiednio identyfikator wierzchołka, identyfikator krawędzi oraz koszt przebycia przez krawędź. Oczywiście do wizualizacji takiego wyniku np. w QuantumGIS trzeba jeszcze dołączyć informacje z kolumny geom_way (współrzędne punktów pośrednich między skrzyżowaniami). Można to zrobić zapytaniem:
select q.*, geom_way from hh_2po_4pgr, (select * from shortest_path(
'select id, source, target, cost from hh_2po_4pgr',
(select source from hh_2po_4pgr order by sqrt((x1 - 20.998746)*(x1 - 20.998746) + (y1 - 52.231591)*(y1 - 52.231591)) limit 1),
(select target from hh_2po_4pgr order by sqrt((x2 - 19.938333)*(x2 - 19.938333) + (y2 - 50.061389)*(y2 - 50.061389)) limit 1),
false,
false)) as q
where edge_id = id;
Aby zapisać wynik można utworzyć widok lub tabelę:
create table wynik as
select q.*, geom_way from hh_2po_4pgr, (select * from shortest_path(
'select id, source, target, cost from hh_2po_4pgr',
(select source from hh_2po_4pgr order by sqrt((x1 - 20.998746)*(x1 - 20.998746) + (y1 - 52.231591)*(y1 - 52.231591)) limit 1),
(select target from hh_2po_4pgr order by sqrt((x2 - 19.938333)*(x2 - 19.938333) + (y2 - 50.061389)*(y2 - 50.061389)) limit 1),
false,
false)) as q
where edge_id = id;
a następnie zwizualizować trasę w QuantumGIS
Zmiana algorytmu wyszukującego drogę na A* wymaga dodatkowo podania kilku kolumn (współrzędnych punktów startowych i końcowych segmentu) – na szczęście osm2po przygotowało te dane do bezpośredniego użycia:
create table wynik as
select q.*, geom_way from hh_2po_4pgr, (select * from shortest_path_astar(
'select id, source, target, cost, x1, y1, x2, y2 from hh_2po_4pgr',
(select source from hh_2po_4pgr order by sqrt((x1 - 20.998746)*(x1 - 20.998746) + (y1 - 52.231591)*(y1 - 52.231591)) limit 1),
(select target from hh_2po_4pgr order by sqrt((x2 - 19.938333)*(x2 - 19.938333) + (y2 - 50.061389)*(y2 - 50.061389)) limit 1),
false,
false)) as q
where edge_id = id;
Jak widać po przebrnięciu przez instalację i konfiguracje sam proces routingu sprowadza się do wywołania pojedynczej funkcji w języku SQL. Nic tylko udostępnić interfejs przez internet i stworzyć własną nawigację online 😉
