pgrouting paikkatietomies

PgRouting miehen tiellä pitää – avoimen lähdekoodin vaihtoehto reititykseen

Verkostoanalyysit ovat eräs paikkatietoanalyysien muoto. Verkostoanalyysien avulla voidaan esimerkiksi laskea reitti kahden eri pisteen välille, muodostaa saavutettavuusvyöhykkeitä ja ratkoa kauppamiehen ongelmaa. Tässä artikkelissa tutustutaan avoimen lähdekoodin reitityskirjasto pgRoutingiin, jonka avulla on mahdollista toteuttaa kaikkia yllä mainittuja verkostoanalyyseja.

PgRouting on PostgreSQL-tietokannan lisäosa, joka mahdollistaa verkostoanalyysien toteuttamisen PostgreSQL-tietokannassa. Verkostoanalyysin pohjaksi tarvitaan reitityskelpoinen tieverkkoaineisto, joka tässä tapauksessa on Liikenneviraston avoimena datana julkaistava Digiroad-aineisto (julkaisu 3/2017).

PgRouting-lisäosalla varustettua reitityskelpoista tietokantaa voi käskyttää itse kirjoitetettujen tietokantakyselyiden sijaan myös QGIS-paikkatietosovellukseen saatavilla olevan (kirjoitushetkellä) kokeellisen lisäosan avulla.

Reititystietokannan luonti

Ennen varsinaisen reitityksen pariin pääsyä tarvitaan hieman esivalmistelua. Mikäli reititystä aikoo tehdä PostgreSQL-tietokannassa, täytyy PostgreSQL-tietokanta olla luonnollisesti asennettu koneelle. Myös PostGIS-lisäosa on hyvä olla asennettuna, sillä tämän artikkelin esimerkki hyödyntää paria PostGIS-laajennoksen spatiaalifunktiota, jotka eivät toimi mikäli PostGIS-lisäosa ei ole asennettu.

Allekirjoittaneen koneessa oli artikkelin laadintahetkellä PostgreSQL-tietokannan versio 9.6, PostGIS-liitännäisen versio 2.3.2 ja pgRouting-liitännäisen versio  2.3.2, joten ainakin em. PostgreSQL+PostGIS+pgRouting -versioiden yhdistelmällä artikkelissa esitetyt ohjeet ovat päteviä. PgRoutingin versioiden kanssa kannattaa muutenkin olla tarkkana, sillä mm. reititykseen käytettävien funktioiden nimet (esim. shortest_path > pgr_dijikstra) ovat saattaneet muuttua vanhempiin versioihin nähden.

 

PgRouting-kirjastolla onnistuu reititys vallan hyvin, joskin moottoriajoneuvojen kanssa vastaan tulevien erikoistilanteiden hanskaaminen vaatii vielä reititystietokannan jatkojalostamista.

 

Reititystä varten kannattaa pyhittää ihan oma tietokanta (artikkelin esimerkissä reititys), johon sitten asennetaan PostGIS- ja pgRouting-lisäosat. Alla komennot, joilla lisätään liitännäiset PostGIS ja pgRouting reitititystietokantaan.  Lopuksi luodaan vielä skeema (reititys), jonne nostetaan (myöhemmin artikkelissa) reitityksessä käytettävä tieverkkoaineisto. Kyselyt voidaan ajella PostgreSQL-kantaan esimerkiksi pgAdmin- tai psql-tietokannanhallintatyökalun kautta.

CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;
CREATE SCHEMA reititys;

Reitityskelpoisen tieverkon tarjoaa Liikennevirasto

Kuten jo ylempänä mainitsin, hyödynnetään tämä artikkelin esimerkissä Liikenneviraston tuottamaa tieverkkoaineisto Digiroadia. Digiroad on kansallinen katu- ja tieverkon tietojärjestelmä, jota ylläpitää ja tuottaa Liikennevirasto. Digiroadiin on koottu koko Suomen tie- ja katuverkon keskilinjageometriat sekä useita eri tyyppisiä ominaisuustietoja (esim. liikennemerkit ja joukkoliikenteen pysäkit).

Digiroad on avointa aineistoa, jota kuka tahansa voi ladata käyttöön Liikenneviraston paikkatietoaineistojen katselu- ja latauspalvelusta. Tähän väliin on pakko todeta kiitollisena paikkatietoaineistojen hyödyntäjänä, että kyllä meidän suomalaisten paikkatietojen hyödyntäjien passaa, sillä Digiroad on laadukas, moneen eri tarpeeseen taipuva tieverkkoaineisto, jonka saa käyttöönsä lyömättä tiskiin euroakaan.

Toinen reitittämiseen soveltuva, avoimesti saatavilla oleva paikkatietoaineisto on Open Street Map, jonka päälle on myös mahdollista rakentaa reititystoiminnallisuuksia pgRouting-liitännäisen avulla. Open Street Map on joukkoistamalla tuotettava kansainvälisen kattavuuden omaava tieverkkoaineisto. Tässä esimerkissä hyödynnetään kuitenkin Digiroadia joten pidemmittä puheitta aineistoja latailemaan.

Digiroad-aineistojen lataaminen
Digiroad-aineistojen latausikkuna Liikenneviraston latauspalvelussa.

Aineistojen laataamiseen ei tässä yhteydessä syvennytä sen suuremmin, sillä aineistojen lataaminen Liikenneviraston latauspalvelusta on vaivatonta ja onnistuu takuulla jokaiselta. Aineistot on saatavilla ZIP-paketoituna, joten ennen aineistojen jatkokäsittelyä tulee ne purkaa johonkin sopivaan sijaintiin työasemalla.

Digiroad-aineistona on monipuolinen ja sisältää paljon erilaisia tieverkkoon liittyviä tietoja. Reitittämisen näkökulmasta tärkein Digiroad-paketin sisältämä aineisto on DR_LINKKI_K, joka sisältää reitittämisen kannalta keskeiset tielinkkigeometriat. Em. tielinkit ovat aineistopaketin KokoSuomi_DIGIROAD_K_EUREF-FIN -kansiossa.

 

Digiroad on laadukas, moneen eri tarpeeseen taipuva tieverkkoaineisto, jonka saa käyttöönsä lyömättä tiskiin euroakaan.

 

Tieverkkoaineiston nosto reitityskantaan

Digiroad-aineistossa Suomi on jaettu 32:een kansioon, joten aineistojen jumppaaminen käsipelissä PostgreSQL-tietokantaan ei ole mielekäs vaihtoehto. Aineistot voidaan nostaa kätevästi PostgreSQL-tietokantaan sarjakäsittelynä GDAL-kirjastoon kuuluvaa ogr2ogr:ää ja Windowsin komentorivin FOR-silmukkaa hyödyntämällä, jolloin käsityö jää varsin vähälle.

Kannattaa huomioida, että /R -parametrin avulla FOR-silmukka käsittelee myös alikansiot, joten komento kannattaa ajaa siinä hakemistossa, jossa 32 kansiota sijaitsevat. Seuraavassa komento, jolla kaikki Digiroad-aineiston 32 DR_LINKKI_K-nimistä shapefileä nostetaan yhteen PostgreSQL-tauluun (reititys.digiroad).

FOR /R %f IN (DR_LINKKI_K.shp) DO ogr2ogr -update -append -a_srs EPSG:3067 
-nlt MULTILINESTRING -lco GEOMETRY_NAME=geom -lco FID=id -lco SCHEMA=reititys 
-f PostgreSQL "PG:host=localhost port=5432 user=postgres dbname=reititys password=postgres" 
-nln reititys.digiroad %f

Pari sanaa komennon parametreista lienee tässä välissä paikallaan. Parametri -nlt MULTILINESTRING määrittää tietokantatauluun luotavan geometriakentän tyypiksi moniosaiset viivat (tällä ei tosin ole merkitystä pgRouting-kirjaston pgr_dijikstra-funktiota käytettäessä, sillä reititysfuktio on kiinnostunut ainoastaan solmutaulun sisällöstä).

Tason luomisasetuksilla (lco = Layer Creation Option) määritellään puolestaan mm. geometriasarakkeen ja pääavaimena toimivan sarakkeen nimet sekä kohteena olevan tietokantaskeeman nimi. Komennon voi ajella esimerkiksi QGIS-asennuksen mukana tulevalla OSGeo Shell -komentorivillä.

Tieverkkoaineiston esivalmistelu reitityskannassa

Digiroad-aineiston sisältämät geometriat sisältävät tiedon kohteen korkeudesta (z-arvo N60 korkeusjärjestelmässä). PgRouting reitityskirjastolle tällaiset geometriat eivät kuitenkaan uppoa, joten Digiroad-aineistoa tulee hieman muokata ennen kuin se soveltuu pgRouting-kirjastolla reititettäväksi. Eräs tapa ratkaista tämä ongelma, on pakottaa geometriat kaksiulotteiseen avaruuteen PostGIS-tietokannan ST_Force2D-funktiolla. Alla esimerkki ko. ratkaisun toteuttamiseksi:

ALTER TABLE reititys.digiroad 
 ALTER COLUMN geom TYPE geometry(LineString,3067)
 USING ST_Force2D(geom)
;

Reititystopologioiden luonti tietokannassa tehdään pgRouting-kirjastoon kuuluvan pgr_createTopology-funktion avulla. Parametreiksi ko. funktiolle annetaan tieverkkogeometriat sisältävän taulun relaatio (reititys.digiroad), toleranssi solmujen etsinnälle (0.0001), geometriasarakkeen nimi (geom) ja tieverkkogeometriat sisältävän taulun id-kenttä (id).

Toimiakseen ko. funktio vaatii lisäksi, että tielinkit sisältävään tauluun on luotu sarakkeet source ja target. Näiden sarkkeiden tietotyypiksi voidaan antaa vaikkapa kokonaisluku (integer). Alla komennot, joilla luodaan ensiksi source- ja target-sarakkeet ja ajetaan tämän jälkeen pgr_createTopology-funktio.

ALTER TABLE reititys.digiroad 
 ADD COLUMN source integer;
ALTER TABLE reititys.digiroad 
 ADD COLUMN target integer;

SELECT pgr_createTopology('reititys.digiroad', 0.0001, 'geom', 'id');

Reititystopologioiden luominen koko Suomen tieverkkoaineistot sisältävän tietokantatauluun ottaa oman aikansa, joten kyselyn ajon aikana ei kannata suuremmin hötkyillä. Onnistuneen ajon seurauksena funktio palauttaa käyttäjän nähtäville arvon PASS.

Onnistuneen suorituksen merkiksi tietokantaan ilmestyy lisäksi tieverkon solmupisteet (solmutaulu) sisältävä taulu digiroad_vertices_pgr. Kyseinen taulu sisältää yli 3,1 milj. riviä, joten hakujen nopeuttamiseksi kannattaa varmistua, että source- ja target-sarakkeet ovat indeksoitu. Näin pitäisi olla, sillä pgr_createTopology-funktio luo oletusarvoisesti em. sarakkeille indeksit. Mikäli indeksit jäävät syystä tai toisesta puuttumaan (esim. käytössä vanhempi pgRouting-kirjasto, jossa tätä ei tehdä automaattisesti), voi sarakkeet indeksoida seuraavilla komennoilla:

CREATE INDEX IF NOT EXISTS digiroad_vertices_pgr_the_geom_idx ON reititys.digiroad("source");
CREATE INDEX IF NOT EXISTS digiroad_vertices_pgr_the_geom_idx ON reititys.digiroad("target");

Mikäli pgr_createTopology-funktion ajo syystä tai toisesta epäonnistuu (esim. geometriat eivät ole kaksiulotteisia tai parametrien nimissä typoja) käyttäjän nähtäville palautuu arvo FAIL. Mikäli silmiesi eteen tulostui onnistumisesta kertova viesti, on reitittämiseen soveltuva tietokanta nyt esivalmisteltu ja varsinainen verkostoanalysointi pgRoutingin avulla voidaan aloittaa.

 

Tässä esimerkissä on käytetty QGIS-paikkatietosovellusta, joka on yhdistetty paikalliseen reititystietokantaan.

 

Lyhintä reittiä etsimässä

PgRouting-kirjaston avulla on mahdollista toteuttaa useita erilaisia verkostoanalyyseja. Tässä artikkelissa lasketaan lyhin reitti kahden pisteen välille. Lyhimmän reitin laskenta onnistuu pgRouting-kirjastoon kuuluvan pgr_Dijikstra-funktion avulla. Kyseinen funktio määrittää lyhimmän reitin ns. kustannus-faktoria minimoiden.

Kustannus-faktorilla tarkoitetaan käytännössä sitä, että toimiakseen pgr_Dijikstra-funktio tarvitsee kustannusarvon (cost) jokaiselle reitittämiseen käytettävälle tielinkkigeometrialle. Määriteltäessä lyhintä reittiä, kannattaa kustannukseksi määritellä tielinkin pituus. Tielinkin pituus voidaan laskea kätevästi PostGIS-liitännäisen ST_Lenght-funktiota hyödyntäen osapuilleen seuraavalla tavalla.

ALTER TABLE reititys.digiroad 
 ADD COLUMN pituus integer
; 

UPDATE reititys.digiroad 
 SET pituus = ST_Length(geom)
;

Lähtö- ja kohdepisteen määrittely

Reitin lähtöpisteeksi valittiin Tampereen keskustoria lähin piste (entisen Viistokadun ja Hämeenkadun kulma) ja kohdepisteeksi Joensuun toria lähin piste (Koskikadun ja Torikadun kulma). Lähtö- ja kohdepisteet tulee etsiä ns. solmutaulusta eli pgr_createTopology-funktion luomasta digiroad_vertices_pgr-taulusta.

Solmutaulusta poimitaan haluttujen lähtö- ja kohdepisteiden id:t, joita tarvitaan varsinaista reittiä laskettaessa. Solmutaulun pisteiden ja niihin id-kentän arvojen etsiminen onnistuu helpoiten jonkin PostgreSQL-tietokantaa lukevan paikkatietosovelluksen ja sopivan taustakartan avulla. Tässä esimerkissä on käytetty QGIS-paikkatietosovellusta, joka on yhdistetty paikalliseen reititystietokantaan. Taustakarttana hyödynnetään Maanmittauslaitoksen taustakarttaa WMS-rajapinnalta.

pgRouting lähtöpiste
Lähtöpisteen (Tampereen Keskustori) id solmutaulussa on 224543
pgRouting kohdepiste
Kohdepisteen (Joensuun tori) id solmutaulussa on 450120.

Sitten kun sopiva lähtö- ja kohdepiste on saatu valittua, on aika alkaa ihmettelemään itse lyhimmän reitin palauttavaa reitityskyselyä. Pgr_Dijikstra-funktio itsessään palauttaa ainoastaan ne solmutaulun pisteet, joiden kautta reitti kulkee, joten sillä ei vielä kuuhun mennä.

Reitin visualisoimiseksi tarvitaan lisäksi viivageometriat reititys.digiroad-taulusta. Viivojen liittäminen pgr_Dijikstra:n valitsemiin solmutaulun pisteisiin toteutetaan tietokantataulujen välisellä id-arvoihin perustuvalla liitoksella (JOIN). Huomiota tulee kiinnittää lisäksi siihen, että pgr_Dijikstra-funktio syö kustannus-faktoria sisään ainoastaan float8-tietotyypissä. Kustannus-faktorin sisältävä pituus-sarake (luotu aikaisemmin) on tyyppiä integer, joten pieni tietotyypin muunnos (CAST) on siis paikallaan.

Äskeisessä vaiheessa etsimämme lähtö- ja kohdepisteiden id-arvot syötetään reitityskyselyssä oranssilla värillä ja alleviivauksella merkittyihin kohtiin siten, että lähtöpisteen id-arvo (224166) tulee ennen kohdepisteen id-arvoa (438422). Lisähuomiona todettakoon, että reititys halutaan toteuttaa ainoastaan sellaisia teitä pitkin, joita voi ajella autolla, joten reitin laskentaan käytettävää tieverkkoaineistoa suodatellaan hieman WHERE-ehdossa.

Suodatus toteutetaan valitsemalla mukaan ainoastaan sellaiset tielinkkigeometriat, joiden toiminnallinen luokka mahdollistaa autolla liikennöimisen. Lisätietoja Digiroad-aineiston tietosisällöstä voi lukea Digiroad – tietolajien kuvaus -dokumentista (toiminnallisen luokan kuvaus löytyy sivuilta 10-12). Kyselyn palauttama reittigeometria halutaan tallentaa uuteen tauluun, joten luodaan uusi taulu (CREATE TABLE … AS) valinnasta.

CREATE TABLE reititys.reitti_tre_to_jns AS
 SELECT
  seq,
  id1 AS node,
  id2 AS edge,
  cost,
  geom
 FROM
  pgr_dijkstra
   (
    '
     SELECT
      id,
      source,
      target,
      pituus :: float8 AS cost
     FROM
      reititys.digiroad
     WHERE
      toiminn_lk NOT BETWEEN 6 AND 8
    ',
    224166,
    438422,
    false,
    false
   ) AS solmut
 JOIN
  reititys.digiroad verkko
 ON
  solmut.id2 = verkko.id
 ;

Kyselyn palauttama reittigeometria on visualisoitu kartalle alla olevassa kuvassa. Kuten kuvasta voidaan havaita, näyttää reitti isossa kuvassa varsin kelvolliselta. Mikäli reittia tarkastellaan tarkemmin, havaitaan siinä muutamia ongelmia.

Tällaisia ovat mm. yksisuuntaiset tieosuudet, joita nykyinen reititystoteutus ei vielä osaa ottaa huomioon. Konkreettinen esimerkki tästä on esimerkiksi Teiskontien ja VT9:n risteys Tampereella, jossa reitti oikaisee vastaantulevien kaistaa myöten VT9:lle.

pgRouting reittigeometria
Tältä näyttää reitti Maanmittauslaitoksen taustakartan päällä visulialisointuna.

Lopputulema

PgRouting-kirjastolla onnistuu reititys vallan hyvin, joskin moottoriajoneuvojen kanssa vastaan tulevien erikoistilanteiden hanskaaminen vaatii vielä reititystietokannan jatkojalostamista. PgRouting-kirjastosta löytyykin lupaavalta kuullostava pgr_analyzeOneway-funktio, jonka nimi lupaa ainakin jotakin yksisuuntaisten analysoinnin varalle.

Digiroad-aineisto sisältää tiedon tielinkin liikennöintisuunnasta (liikennevirran suunta), joten jatkokehitysideaksi voisi ajatella reititystietokannan jalostamista sellaiseksi, että se huomioi yksisuuntaiset ja mahdolliset kääntymisrajoitukset. Myös kääntymisrajoituksiin löytyy kättä pidempää Digiroad-aineistosta, sillä Digiroad-aineistojakeluun kuuluu kääntymisrajoitukset sisältävä aineisto, joka on linkitettävissä tielinkit sisältävään aineistoon.

Millaisia verkostoanalyyseja sinä olet tehnyt pgRouting-kirjaston avulla?

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *