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 lisäksi reitityskelpoinen tieverkkoaineisto, joka tässä tapauksessa on Liikenneviraston (nykyään Väylävirasto) avoimena datana julkaistava Digiroad-aineisto.
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.
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.
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.
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.
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.
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.
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.
