Mitkä ihmeen Folkoot? FOSS4G + talkoot = Folkoot!

Avoin lähdekoodi on Gispon liiketoiminnan kovaa ydintä. Olemme jo aiemminkin tukeneet yhteisöä monella eri tavalla. Sponsoroimme projekteja ja tapahtumia suoraan rahallisesti ja jaamme kaikki asiakasprojekteissa tehdyt tuotokset avoimesti aina kun se on mahdollista. Avoimen lähdekoodin kentällä kuitenkin voi helposti käydä niin, että ottaa enemmän kuin antaa ja me haluamme ehdottomasti olla siellä antavalla puolella. Siksi haluamme entistä organisoidummin kontribuoida meille keskeisiin projekteihin myös ns. normaalin työpanoksen lisäksi. 

Ajatuksena on tehdä paremmin näkyväksi se panostus, jonka näille projekteille tarjoamme. Itsellemme ja myös muille. Folkoo-hengessä gispolaiset voivat allokoida viisi prosenttia kokonaistyöajastaan avoimen lähdekoodin projekeihin kontribuoimiseen. Tämä saattaa kuulostaa vähältä ajallisesti, mutta kun tälle laitetaan hintalappu, se kuulostaakin aika mahtavalta panostukselta. Nykyisellä työntekijämäärällämme tämä tarkoittaisi konsultointityön hinnoittelulla pitkälle  yli 100 000 euron panostusta vuosittain. Mittasuhteita tälle antaa esimerkiksi se, että QGIS-projektin korkein Flagship-sponsoritaso on vuosittain 27 000 € hintainen. 

Yhteisön osana voi olla monella tavalla

Helteisenä kesäkuun perjantaina lähdimme toteuttamaan ensimmäisiä sisäistä Folkoot-tapahtumaamme. Aloitimme päivän yhteisellä alustuksella, jossa kävimme läpi muutamia tapoja kontribuoida päivän aikana. Osalla oli jo oma miniprojekti mielessä tai issue ratkottavana, mutta yhdessä kävimme läpi eri tapoja osallistua ja mietimme kaikille sopivaa tekemistä. 

Yksi esimerkki matalan kynnyksen kontribuutiosta on muiden avaamien issueiden replikointi ja testaaminen. Käytännössä siis joku käyttäjä on huomannut esimerkiksi ohjelmistossa virheen ja kirjannut sen kehittäjille korjattavaksi. Testaamalla ja validoimalla näitä ongelmia, voidaan testaajille antaa lisätietoja mahdollisesta ongelmasta ja varsinainen korjaus helpottuu huomattavasti. Kaikki jotka osaavat käyttää ohjelmistoa ja pystyvät seuraamaan ohjeita voivatsiis tällä tavalla tuoda oman panoksensa pöytään vaikka C++:lla ohjelmointi tai binäärikirjastojen kääntäminen ei olisikaan omaa juttua. Myös dokumentaation kirjoitus ja käännöstyö ovat arvokkaita töitä joihin kaikki pystyvät osallistumaan. Tietysti varsinainen ohjelmistokehitys ja esimerkiksi bugien korjaaminen on erittäin arvokas panos ja se on myös keskeinen osa Gispon Folkoot-filosofiaa. 

Yhden työpäivän aikana saatiin todella paljon aikaan. Useita QGISin tikettejä suljettiin, myös muutamia uusia issueita avattiin, mutta niiden syntyjä lähdettiin myös etsimään lähdekoodista. StackExchangessa vastailtiin useisiin kysymyksiin, QGIS-projektia käännettiin suomeksi ja tekipä Mikael myös pull requestin pygeoapiin. Avoimen lähdekoodin lisäksi toimintamme ytimessä on avoin data ja erityisesti OpenStreetMap, joten Folkoot soveltuivat hyvin myös HOT-OSM:n digitointiin. Muutama Gispon kehittäjä ratkoi bugeja parityöskentelynä, joka on erityisen hyvä menetelmä osaamisen jakamisessa ja ongelmien ratkomisessa. 

Folkoohenkeä myös jatkossa

Päivän päätteeksi kävimme läpi miten kukin oli aikansa käyttänyt ja mitä oli saanut aikaan. Kollegoiden omatoimisuus ja aktiivisuus oli jo ennestään tiedossa, mutta silti se ylitti odotukset ja oli mahtavaa seurattavaa. Tärkeänä lopputuloksena tunnistimme yhdessä kuinka tällä tavalla pystyttiin madaltamaan kynnystä kontribuoida suoraan projekteihin. Yhteisöt ovat aidosti avoimia ja jos me emme niitä issueita avaa ja sulje, niin kukas sitten? Analogia perinteisiin talkoisiin tuntui toimivan myös oikein hyvin: kaikki tekivät sen mitä osasivat ja toivat pöytään oman panoksensa.  

Folkoot palvelivat tarkoitustaan erinomaisesti ja kuukausittainen talkoopäivä jää pysyväksi osaksi työskentelyä Gispolla. Haluankin haastaa muut alan toimijat mukaan folkoilemaan! Olet sitten töissä paikkatietoalan konsulttitoimistossa tai julkisen sektorin organisaatiossa, konsepti on siirrettävissä kaikkialle. Sen lisäksi, että tällä tavalla voi tarjota panoksensa avoimen lähdekoodin projekteille, oppii siinä sivussa myös paljon uutta lyhyessäkin ajassa. Kirsikkana kakun päällä, on yhdessä kehittäminen ja ongelmien ratkominen myös hauskaa. 

Aiemmin kirjoitimme, että Gispo on osallistunut HSL:n uuden Reittioppaan kehittämiseen ja samassa yhteydessä mainitsimme, että työtä on vielä tehtävä, jotta sovellus olisi erityisryhmille, kuten näkövammaisille ja liikuntarajoitteisille, sopiva. HSL onkin tehnyt ja tekee edelleen työtä Reittioppaan ja monien muiden, kuten Mobiililippu-sovelluksen, esteettömyyden parantamiseksi. HSL mm. tilasi keväällä Annanpuralta näkövammaisille suunnatut käytettävyystutkimukset Mobiililippu- ja Reittiopas-sovelluksille ja tutkimuksien tulokset ovat juuri valmistuneet tai valmistumassa. Myös Gispo oli toukokuussa mukana HSL:n esteettömyystyössä.

OPENSTREETMAP JA ESTEETTÖMYYS

Gispo selvitti toukokuussa muun työn ohella erityisesti OpenStreetMapin osalta miten Reittiopasta voitaisiin parantaa erilaisten erityisryhmien näkökulmasta. Tuloksena työstä syntyivät yhteenvetokalvot sekä wiki-sivu, joista muun muassa selviää, että OpenStreetMapiin voi lisätä vaikkapa hissejä wheelchair=yes -tagien kera, ramp=yes -tageja erilaisten luiskien merkitsemiseen tai traffic_signals:sound=yes -tageja äänimerkillisille liikennevaloille.

HSL jatkaa esteettömyystyötä sovellustensa parissa ja myös Gispo toivottaa erittäin tervetulleiksi kaikki OpenStreetMapin esteettömyyteen liittyvät näkemykset ja ideat.

Älypuhelimen karttasovelluksen avulla löydämme helposti reitin vieraaseen paikkaan tai lähimmän huoltoaseman uudella seudulla. Paikkatieto on kuitenkin paljon muutakin kuin navigointia. Paikkaan sidotun tilasto- tai havaintoaineiston analysoimisesta on hyötyä kaikilla aloilla. Yritykset keräävät dataa asiakkaistaan, hallinnoivat projektejaan ja omaisuuttaan tai seuraavat toteutumaa ja suunnittelevat tulevaa. Kaikessa tässä paikkaulottuvuuden mukaan ottaminen tehostaa analyyseja ja voi paljastaa uusiakin asioita. 

Tilannekuva kertoo, mitä, missä ja milloin tapahtuu. Pääpaino on nykyhetkessä: mikä on tilanne juuri nyt? Vuoden kestänyt pandemia on varmasti viimeistään tehnyt tartuntojen tilastoteemakartoista, rokotekattavuuden kehittymisestä ja liikkumisanalyyseista tuttuja meille kaikille. Sama periaate on monissa muissa tilastoissa. Asukkaiden ikä- ja tulorakenne, asuntojen hintojen kehitys, muuttovoitto ja -tappio jne. ovat kaikki sijaintiin sidottua tilastotietoa. Siis paikkatietoa. Gispon asiakkaiden kirjo kuvastaa hyvin paikkatietojen hyötyjen monipuolisuutta: olemme tukeneet eri projekteissamme viime aikoina esimerkiksi ilmanlaatu-, matkailupalvelu-, kaavoitus– ja liikennedatan hyödyntämistä.

Tilannekuva ei kuitenkaan itsessään selitä, miksi jotain tapahtuu. Paikkatietojen monipuolisuus avautuukin kunnolla vasta analysointivaiheessa. Tilastotieteestä tutut menetelmät, esimerkiksi klusterit, regressioanalyysit ja erilaiset luokittelumenetelmät ovat kaikki sovellettavissa paikkatietoihin. Lisäksi käytettävissämme on ihan uusi ulottuvuus: eri aineistojen ja tekijöiden väliset sijainnilliset yhteydet. Vaikka kahdella ilmiöllä ei näyttäisi olevan esimerkiksi ajallisesti mitään yhteyttä, sijaintitarkastelu saatta paljastaa yllättäviäkin riippuvuuksia niiden välillä. 

Jotta eri aineistoja voidaan analysoida yhdessä, täytyy tietolähteiden yhteiskäytön olla sujuvaa. Paikkatieto-ohjelmistolle erilaiset tiedostoformaatit, aluejaot, aikasarjat ja koordinaattijärjestelmät eivät ole ongelma. Monipuolisia, ajantasaisia aineistoja saa rajapinnoista usein avoimesti ja ilmaiseksi. Suomessa esimerkiksi Tilastokeskus, Suomen ympäristökeskus, Kuntaliitto ja yksittäiset kunnat sekä yliopistot ja muut tutkimuslaitokset julkaisevat aineistojaan hyödynnettäväksi avoimesti, myös kaupallisiin tarkoituksiin. Toki tarjolla on muutakin kuin tilastodataa: Maanmittauslaitoksen korkeusmalli, Väyläviraston tietyöt ja kaupunkien kaavoitustiedot ovat vain muutamia esimerkkejä avoimen datan monipuolisuudesta.

Koska analyyseja tehdään aina päätöksentekoa varten, niiden tulosten täytyy olla ihmiselle ymmärrettäviä. Paikkatieto-ohjelmistolla tietokoneen laskemat tunnusluvut voidaan visualisoida helppolukuiseksi, datan tärkeitä piirteitä korostavaksi kartaksi tai infografiikaksi. Kun paikkatietojen tuottama uusi informaatio siirtyy kokoushuoneen kalvoille tai verkkosivun karttapalveluun, sen voima kirkastuu koko organisaatiolle ja se voi tuottaa lisäarvoa. 

Paikkatietoja hyödyntämällä voi optimoida ja tehostaa organisaation toimintoja. Hyvänä esimerkkinä tästä on logistiikka, jossa kuljetusten reittisuunnittelulla voidaan säästää kuljetuskustannuksissa sekä vähentää hiilidioksidipäästöjä. Toinen perinteinen käyttötapaus on esimerkiksi toimipisteen sijaintisuunnittelu – millaisia resursseja toimipiste tarvitsee ja millainen asiakaskunta tai muu toimittajaverkosto läheltä löytyy? Vastaava toteutus julkisella puolella voi olla vaikkapa uuden koulun sijoittaminen sopivalle alueelle huomioiden väestöpohjan tai ambulanssien asemapaikkojen määritys. Kunnossapito ja omaisuudenhallinta on myös tehokasta toteuttaa karttapohjaisesti, jolloin pääkäyttäjät näkevät nopeasti minne huoltotoimenpiteitä pitää kohdentaa. Paikkatietoja voidaan käyttää myös viestinnän ja markkinoinnin välineenä – esimerkiksi houkutella matkailijoita tutustumaan alueen palveluihin.

Jos lähdetään liikenteeseen aivan alkuvaiheesta ja perustetaan vasta organisaation paikkatietojärjestelmiä on hyvä huomioida, että toteutus vaatii aikaa ja osaajien kouluttamista. Täysi hyöty paikkatietojen käytöstä voi näkyä organisaatiossa vasta ajan kuluessa. Siksi kannattaakin lähteä liikenteeseen pienin askelin ja vaikkapa määritellä tärkeimmät haasteet ja miten ne ratkaistaan sekä kouluttaa pääkäyttäjät ja tukea heitä työssään.

Gispolla teemme töitä avoimen lähdekoodin paikkatietoratkaisujen parissa. Niissä hyötynä on pienet aloituskustannukset, koska työkalut ovat testattavissa ja käytettävissä ilmaiseksi. Niitä voi räätälöidä organisaation omiin tarpeisiin, jolloin on kuitenkin huomioitava kehittämisen ja ylläpidon kustannukset. Avoimen lähdekoodin maailmassa tärkeää onkin osata valita oikeat työkalut sekä ymmärtää yhteiskehittämisen potentiaali, joka parhaimmillaan tuo kehitykseen tukea globaalisti. Hyviä esimerkkejä avoimen lähdekoodin työkaluista, jotka ovat monien meidän käytössä ovat mm. Linux- ja  Android-käyttöjärjestelmät, Suomessa kehitetty Reittiopas tai vaikkapa Omaolo-palvelu. Paikkatietopuolella käytetyimpiä työkaluja ovat työpöytäohjelmisto QGIS, tietokantapuolella PostgreSQL/PostGIS ja aineistojen julkaisupuolella GeoServer. Web-karttapalveluita taas on todella monipuolisesti saatavilla eri tarpeisiin.

Gispon paikkatietoasiantuntijat auttavat kaikissa näissä vaiheissa – tiedon etsimisessä, muotoilussa oikeaan formaattiin, tiedon analysoinnissa, raportoinnissa ja visualisoinnissa. Lisäksi koulutamme ja tuemme avoimen lähdekoodin paikkatieto-ohjelmistojen käyttäjiä ja teemme ohjelmistojen kehitystyötä, jotta työskentely sujuu yhä joustavammin.

QField on QGISin kenttätyöhön soveltuva sovellus, joka on ilmaiseksi saatavilla Play-kaupasta Android-laitteille. Se on käytännössä mini-QGIS eli sisältää paljon samoja juttuja kuin QGIS itsekin. Kaikkea ei kuitenkaan mobiililaitteella kannata tehdä, joten QField on nimensä mukaisesti suunniteltu kenttätöiden tekoon. 

Teimme Väyläviraston pyynnöstä testausta kevään 2021 aikana siitä, miten QField soveltuu liikenteenohjauslaitteiden tiedonkeruuseen. Liikenteenohjauslaitteilla tarkoitetaan liikennemerkkejä, liikennevaloja ja ajoratamaalauksia.

“Halusimme selvittää open source -välineiden soveltuvuutta tähän tiedonkeruuseen, jota Väyläviraston ja kuntien tulee nyt tieliikennelain mukaan tehdä”

Matti Pesu, Väylävirasto

Tiedonkeruun taustalla käytettiin Väyläviraston liikenteenohjauslaitteiden (tuttavallisemmin LOL) käsitemallia, jonka pohjalta luotiin ensin tietojen tallennusta varten relaatiotietokanta PostGISiin ja sen avulla tuotettiin QGISin avulla työtila lomakkeineen. Tämä on työnkuvana hyvin samanlainen mitä tällä hetkellä Gispolla muutenkin tehdään: tietojen hallinta PostGISissä, QGIS toimii käyttöliittymänä. Nyt vain vietiin asia askeleen eteenpäin eli kentälle. 

Projektissa testasimme Tampereen infra Oy:n, Nurmeksen, Kouvolan ja Ylöjärven kanssa miten käytännön työ QFieldin ja LOL-tietokannan kanssa toimi. Projektin havainnot on koottu yhteen loppuraporttiin sekä ohjeet QFieldin käyttöön sekä offline moodissa että PostGISin kanssa löytyy Väyläviraston GitHubista. 

Havaintoja LOL-tietomallista ja QFieldistä

LOL-käsitemallia ei oltu aiemmin testattu ns. fyysisen toteutuksen kanssa ja tämä oli ensimmäinen kerta, kun tietoja pystyttiin tallentamaan sen mukaisesti. Tässä QGIS ja PostGIS toimivat hienosti yhteen. Nyt kun työtila QGISille on tehty, voi sitä käyttää myös ilman QFieldiä haluttaessa. 

Itse LOL-tietokanta on hyvin kattava ja liikennemerkkejä on paljon, siksi niiden etsiminen pitkästä listasta oli vähän haastavaa, mutta jos liikennemerkin nimen tiesi, työkalu mahdollisti sen hakemisen listalta. Testaajia mietitytti mm. alueellisuus – porovaroituksia kun ei ihan joka paikasta löydy.

Muutenkin kenttätyöhön koko LOL-tietomalli oli aika laaja. Käytännön työssä varmasti prosessista karsiutuu pois suuri osa tietokentistä ja käyttäjät luultavasti täyttävät kentällä vain pakolliset ja jatkavat tietojen täyttöä lämpimissä ja ilmastoiduissa sisätiloissa. 

Mittatarkkuuslaitteilla saatiin todella tarkkaa sijaintitietoa tallennettua QFieldin avulla ja tietojen tallennus yhteiseen tietokantaan onnistui hyvin. Testaajat suhtautuivat yllättävän positiivisesti sovellukseen, vaikka Gispon paikkatietoväki oli hieman skeptinen miten tässä nyt käy. Lopulta oikein hienosti onnistuttiin kovissa testiolosuhteissa!

Kehitystä ja kehitystoiveita

QFieldiin tehtiin projektissa suomenkielisten osoitteiden haku, kiitos OpenGIS.ch:lle nopeasta työstä! Se hyödyttää nyt kaikkia QFieldin käyttäjiä Suomessa.

QFieldin akilleen kantapää on ollut pitkään se, että sovellukseen pitää erikseen hakea QGISistä paketoitu työtila tiedostona (esim. USB-piuhalla tai nettisivun kulmalta). Tämä aiheuttaa ylimääräisen työprosessin, josta olisi kiva päästä eroon. Tulossa on kuitenkin ratkaisu lähiaikoina QField Cloudin muodossa ja toivottavasti jatketaan sen osalta vielä testailuja.

No toimiiko se?

Loppujen lopuksi voimme hyvillä mielin suositella QFieldiä kenttätöiden tekoon.

Liikenteenohjausmerkkien osalta työkalua kannattaa käyttää tietojen ylläpitoon, ehkä ihan alusta asti 10 000 liikennemerkin keruu kännykällä voi olla aikamoinen urakka. Mutta jos tarpeena on päivittää tietoja, siihen QField toimii hyvin. 

QFieldiä voisimme suositella mihin tahansa kenttätöihin. QGISin avulla valmiit lomakkeet saa todella näppärästi tehtyä eri tarpeisiin. Kunhan QField Cloud tulee, vain taivas on rajana!

Tässä blogisarjan toisessa osassa tarkastellaan avoimen lähdekoodin työkaluja joiden avulla minimaalisen kustannuksen tuottavaa polkua voidaan lähteä etsimään. Blogisarjan edellisessä osassa käsiteltiin aiheeseen liittyvää teoriaa.

Periaatteessa minimikustannuspolun määrittämiseen ei vaadita paikkatieto-ohjelmistoja. Tämä väite on kuitenkin totta oikeastaan vain sellaisissa tilanteissa, joissa käyttäjä saa kustannuspinnan valmiina tai haluaa tarkastella ongelmaa hyvin pitkälle abstrahoidun maailman kautta. Mikäli käyttäjä haluaa käyttää analyysinsa pohjana todellista karttapohjaa tai maastomalleja, QGIS:in kaltainen avoimen lähdekoodin paikkatieto-ohjelmisto on ensiarvoisen tärkeä työkalu kustannuspinnan muodostuksessa. Tämän blogin työkaluvertailussa oletuksena on, että kustannuspintarasteri on jo muodostettu ja tavoitteena on löytää optimaalinen reitti liikkua pitkin tätä rasteripintaa.

QGIS lisäosa Least-Cost path

QGISin lisäosavalikoimasta löytyy ratkaisu useimpiin yleisiin paikkatietohaasteisiin. Sama pätee myös pienimmän kustannuksen tuottavan polun etsimiseen. Paitsi että QGISillä voi tehokkaasti muodostaa varsinaisen kustannuspinnan, edellisessä blogissa kuvatut työvaiheet 2 ja 3 voi myös hoitaa QGIS:n avulla asentamalla QGIS:iin ongelman ratkaisemiseen soveltuvan laajennuksen (Plugins – Manage and Install Plugins – Least-Cost Path).

Laajennuksen käyttö on hyvin yksinkertaista. Laajennukselle annetaan syötteenä kustannuspinta (rasterimuotoisena) sekä aloitus- ja päätepisteet (vektorimuotoisena). Halutessaan voi määrittää tulostiedoston nimen ja valita mihin polkuun tulostiedosto tullaan tallentamaan. Käyttäjä voi myös vaikuttaa hieman laajennuksen toimintalogiikkaan mikäli hän on etsimässä minimikustannuspolkua useasta mahdollisesta päätepisteestä koostuvaan ongelmaan.

+ Helppo käytettävyys
+ Pystyy käsittelemään syötetiedot oletusmuotoisina
+ Tuottaa ratkaisun selkeässä ja havainnollistavassa muodossa
– Hitaus (algoritmin suorittamiseen kuluu 5-10 min koneen tehosta riippuen)

WhiteBox tools: komentorivityökalu rasterianalyyseihin

WhiteboxTools on MIT-lisenssillä varustettu kokoelma analyysityökaluja ja on kehitetty alkujaan Guelphin yliopistossa Kanadassa. WhiteboxTools on komentorivipohjainen hyvin laaja työkalukirjasto, jonka voi asentaa omalle koneelleen standalone asennuksena (binääritiedostot yleisimmille käyttöjärjestelmille löytyvät osoitteesta, mutta myös lähdekoodista asentaminen on mahdollista). Työkalun voi asentaa myös Docker imagesta ja algoritmeja on mahdollista hyödyntää myös QGIS-lisäosan kautta. Kannattaa kuitenkin huomioida, että QGIS-lisäosan ylläpito on lakkautettu ja resurssit on kohdennettu komentorivipohjaisen työkalukirjaston kehittämiseen.

Asennuksen jälkeen  työkalua Whitebox Tools toimii suoraan komentorivin kautta seuraavasti:

1. Kustannusetäisyystiedon tuottaminen

.\whitebox_tools.exe --run=”CostDistance” -v --wd=”path_to_input_data_folder” --source=”start_point.tif” --cost=”cost_rast.tif” --out_accum=”acc_cost.tif” --out_backlink=”back.tif”

2. Pienimmän kustannuksen tuottavan polun etsiminen

.\whitebox_tools.exe --run=”CostPathway” --wd=”path_to_input_data_folder” --destination=”points.tif” --backlink=”back.tif” --output=”path.tif” -v

tai kirjoittamalla yksinkertaisen python-ohjelman ja suorittamalla sen (tallenna skripti samaan kansioon whitebox_tools.exe tiedoston kanssa):

import os
import sys
from whitebox_tools import WhiteboxTools
 
wbt = WhiteboxTools()
 
# Aseta polku syöte- ja tulostetiedostot sisältävään kansioon
wbt.work_dir = os.path.dirname(os.path.abs_path(__file__)) + “\\testdata\\”
 
# Kustannusetäisyystieto
wbt.cost_distance(start_point.tif, cost_rast.tif, acc_cost.tif, back.tif)
 
# Pienimmän kustannuksen tuottava polku
wbt.cost_pathway(points.tif, back.tif, path.tif)

WhiteboxTools määrittää minimikustannuksen tuottavan polun kahdessa osassa. Luonnollinen seuraus tästä on se, että käyttäjä saa tällöin enemmän informaatiota tutkittavasta ilmiöstä. WhiteboxToolseja käyttämällä käyttäjä ei saa tulokseksi pelkkää vektorimutoista ratkaisupolkua vaan myös rasterimuotoiset tiedostot siitä, miten kerrytetty kustannus muuttuu tutkittavassa avaruudessa (acc_cost.tif) ja mistä suunnasta löytyy kunkin ruudun pienimmän kerrytetyn kustannuksen omaava naapuriruutu (back.tif). 

Suurin ongelma WhiteboxToolsin algoritmeissa on, että ne eivät osaa käsitellä vektorimuotoista tietoa. Tämä puute vaikuttaa sekä siihen, miten paljon esikäsittelyä syöteaineistot vaativat että siihen, miten havainnollistavassa muodossa ratkaisu saadaan tuotettua. Kuitenkin, jos puutteen tiedostaa, siihen voi reagoida jo ratkaisuprosessin alkuvaiheessa tuottamalla esimerkiksi QGIS:n avulla kustannusrasterin ohessa myös toisen, dimensioiltaan kustannusrasteria vastaavan ruudukon, jonka ainoat nollasta eroavat ruudut ovat päätepisteet sisältävät ruudut (aloitusruudun / aloitus- ja päätepisteruudun arvoksi voi asettaa minkä tahansa positiivisen vakion).

+ Huomattavasti tehokkaampi kuin QGIS-laajennus
+ Tuottaa paljon relevanttia kustannusetäisyysanalyysitietoa
– Tuki vektoritasojen käsittelyyn puuttuu
– Komentorivipohjainen (riippuu mistä tykkää)

GRASS: vanhassa vara parempi

GRASS on alkujaan jo vuonna 1984(!) kehitetty työkalu spatiaaliseen analyysiin. Se on kuitenkin edelleen aktiivisessa käytössä ja kehityksessä erityisesti tiedeyhteisössä. GRASS GIS on monipuolinen rasteri- ja vektoritiedostomuotojen analysointiin soveltuva ohjelmisto. 

GRASS tarjoaa vaihtoehdon kahden edellisen ratkaisun välimaastoon sijoittuvan vaihtoehdon. GRASS:n suurin vahvuus verrattuna edellä esiteltyihin lähestymistapoihin on se, että se on paitsi erittäin tehokas ja toimiva, myös huomattavasti WhiteboxToolseja käyttäjäystävällisempi. GRASS GIS on yksi QGIS:n ydinlaajennuksista ja sen voi käydä aktivoimassa QGIS:n asetuksista (Settings – Options – Processing – Providers) tai asentaa Plugin Managerin avulla. GRASS GIS:llä on sekä komentotulkkipohjainen että graafinen käyttöliittymä. Minimikustannuspolku saadaan määritettyä molemmilla tavoilla yhtä tehokkaasti.

Hyödyntämällä GRASSin omaa komentoriviä

1. Luo GRASS Mapset (linkki)

2. Vie tarvittava data Grass Mapsettiin syöttämällä GRASS Shelliin

r.in.gdal input=path_to_data/cost_rast.tif output=cost_rast2.tif

v.in.ogr input=path_to_data/start_point.gpkg output=start_point2

v.in.ogr input=path_to_data/end_point.gpkg output=end_point2

3. Suorita kustannusetäisyysanalyysi syöttämällä GRASS Shelliin

r.cost input=cost_rast2 output=acc_cost2 outdir=back2 start_coordinates=x1,y1 stop_coordinates=x2,y2

• start_coordinates=x1,y1 stop_coordinates=x2,y2 tilalle voi laittaa start_points=start_point2 stop_points=end_point2

4. Etsi pienimmän kustannuksen tuottava polku

r.path input=back2 format=degree vector_path=path2 start_coordinates=x1,y1,x2,y2

• start_coordinates=x1,y1,x2,y2 tilalle voi laittaa start_points=start_point2,end_point2

Huomaa, että tieto polun päätepisteistä voidaan antaa koordinaattimuotoisen tiedon lisäksi yhtä hyvin myös rasterimuotoisina karttatasoina (tällöin start_points avainsanan tilalla tulee vain olla start_raster). Myös tulospolun voi tallentaa halutessaan rasterimuotoisena (avainsananana toimii tällöin raster_path).

Hyödyntämällä GRASSin moduuleja

1. Suorita kustannusetäisyysanalyysi

• Processing Toolbox – GRASS – Raster – r.cost
• Mahdollisuus asettaa ylärajan sallitulle kustannukselle (mikäli käyttäjä ei halua määrittää polun päättymispistettä, tulos kertoo minne asti tietyllä resurssilla voi kuhunkin suuntaan edetä)
• Mahdollisuus kontrolloida prosessin suorittamiseen allokoitavan muistin määrää
• Tuottaa kolme tulostiedostoa (kerrytetyt kustannukset, suuntatieto pienimmän kerrytetyn kustannuksen naapuriruutuun ja tieto kustannusten kohdentamisesta)

2. Etsi pienimmän kustannuksen tuottava polku

• Processing Toolbox – GRASS – Raster – r.drain
• Syöteaineistoina toimivat edellisessä vaiheessa ajetun r.cost algoritmin tulostiedostot ja tieto polun päätepisteistä (vähintään aloituspiste tulee antaa syötteenä, mutta myös molemmat on mahdollista antaa, kunhan nämä pisteet sisältyvät samaan karttatasoon)
• Mahdollisuus laskea erinäisiä tunnuslukuja (esimerkiksi polun kokonaiskustannus)
• Tuottaa kaksi tulostiedostoa (ratkaisupolku rasterimutoisena ja vektorimuotoisena)

Huomaa, että vaikka GRASS komentorivin kautta käskyt toimivat millä tahansa QGIS versiolla, niin moduulien kanssa kannattaa käyttää LTR-versiota (esim. QGIS 3.14).

+ Erittäin tehokas (algoritmit menevät läpi sekunneissa)
+ Tuottaa paljon relevanttia kustannusetäisyysanalyysitietoa
+ Tuki niin vektori- kuin rasterimuotoisellekin tiedolle
+ Valittavissa komentorivipohjainen lähestymiskulma tai graafinen käyttöliittymä (ainut eroavaisuus on siinä, että r.path algoritmia ei ole implementoitu graafisen käyttöliittymän työkaluksi, mutta r.drain algoritmilla saa saman asian selville)
– GRASS Mapsetin käyttö, jos halutaan ajaa käskyjä komentorivin kautta

Muut työkaluvaihtoehdot

Myös SAGA tarjoaa minimikustannuspolun määrittämiseen soveltuvia algoritmeja (Accumulated cost, Least cost paths), mutta nämä algorit kärsivät niin vakavista suorituskykyongelmista, ettei niiden avulla pystynyt ratkaisemaan tässä blogissa käsiteltyä esimerkkiongelmaa. Samaan lopputulokseen päätyi myös GDAL & Skimage kirjastoihin perustuva python-ohjelma, jonka suoritus keskeytyi “Killed”-ilmoitukseen. Mainittakoot vielä, että on tietenkin mahdollista ohjelmoida myös itse algoritmi, joka kykenee määrittämään kustannusetäisyys- ja suuntarasteritiedostot ja niiden  perusteella löytämään minimikustannuspolun.

Tällaiset “brute force” algoritmit ovat kuitenkin vaarallisia, sillä mahdollisten polkujen määrä räjähtää helposti käsiin ja ohjelmien ajaminen syö tietokoneen koko muistin ja/tai laskentakapasiteetin. Jonkin verran helpotusta skaalautuvuusongelmiin voi hakea dynaamisesta ohjelmoinnista ja muistia säästävistä rakenteista (mm. priority queue). Kannattaa kuitenkin pitää mielessä, että avoimen lähdekoodin maailmassa on jo olemassa varsin toimivia keinoja pienimmän kustannuksen omaavien polkujen löytämiseen.

Yhteenveto

Tätä klassista paikkatieto-ongelmaa voi ratkoa siis useammalla avoimen lähdekoodin työkalulla. On kuitenkin tärkeä muistaa, että analyysin lopputulos on vain niin hyvä kuin lähtöaineisto. Eli vaikka tässä blogissa ei kustannuspinnan muodostamista käsitelty tarkemmin, se näyttelee keskeistä roolia lopputuloksen luotettavuuden kannalta.

Kenties lähtöaineistojen kerääminen ja muokkaaminen on blogisarjan seuraava osa. Mukavia reitityshetkiä minimikustannuspolkujen parissa!

Saimme Gispolla hiljattain olla mukana kehittämässä todella mahtavaa QGIS-lisäosaa Unfoldedin visualisointialustalle. Työkalu mahdollistaa entistä helpommin interaktiivisten karttojen tuottamisen ja jakamisen osana QGIS-työnkulkua. 

Unfolded on amerikkalainen paikkatietoalan start-up jonka perustajat ovat lähtöisin Uberilta. Unfoldedin toimintamalli on ns. Open core, jonka myötä he ovat vahvasti mukana erityisesti niiden avoimen lähdekoodin projektien kehityksessä, jotka tukevat heidän omaa tuotekehitystään. Tällaisia ovat esimerkiksi kepler.gl, H3 ja deck.gl, joiden kaikkien pääkehittäjät ovat Unfoldedilla töissä. 

Unfolded tarjoaa Unfolded Studio-nimistä visualisointialustaansa palveluna. Kuka tahansa voi tehdä sinne ilmaisen tilin. Tiliin sisältyy peräti gigan verran ilmaista tilaa kartoille ja datoille. Unfolded Studion keskeinen ajatus on datan käsittelyn helppous ja visualisointien näyttävyys. He halusivat tehdä datan julkaisusta Unfolded Studioon entistä helpompaa. Tämän vuoksi kehitimme heille lisäosan, jonka avulla QGIS-käyttäjät voivat julkaista omat paikkatietoaineistonsa ja projektinsa Unfolded Studioon. 

Lisäosan käyttö kulkee pähkinänkuoressa seuraavasti. 

• Lisäosa asennetaan QGISin lisäosavalikosta
• QGIS-projektiin lisätään vektoriaineistoja ja tyylitellään ne
• Unfolded-niminen lisäosa löytyy omasta ikonistaan tai web-valikon alta
• Määritellään lisäosan valikossa interaktiivisen kartan visualisointityylit ja muokataan esimerkiksi otsikot ja kuvaustekstit kuntoon
• Klikkaamalla Export map lisäosa tallentaa valitut datat ja tyylit yhdeksi ZIP-paketiksi käyttäjän omalle koneelle
• Viedään ZIP-paketti omalle Unfolded Studio-tilille import map valikon kautta
• Tehdään mahdolliset lisäviilaukset Unfolded Studion puolella ja kartta voidaan julkaista kaikkein nähtäville yhdellä klikkauksella!

Tällä hetkellä lisäosa tukee perustason tyylejä (täyttövärit, reunat, luokittelut) vektoriaineistoille. Aineisto voi olla missä tahansa koordinaattijärjestelmässä ja missä tahansa QGISin tukemassa vektoriformaatissa. Normaalisti Unfolded Studioon vietävä paikkatietoaineisto on pitänyt olla WGS84-koordinaattijärjestelmässä ja tuetut vektoriformaatit ovat olleet rajallisia. Kehittämämme työkalu helpottaa tätä huomattavasti ja mahdollistaa Unfolded Studioon vietävän datan monipuolisen esikäsittelyn, suodatuksen sekä analyysin kaikilla QGISin monipuolisilla menetelmillä. 

Osana projektia tuotimme muutaman esimerkkivisualisoinnin lisäosan mahdollisuuksista. Tässä alla Helsingin seudun rakennukset väritettynä rakennusvuoden mukaan. Väripaletti on QGISin oma.

Lisäosa on kaikkein ladattavissa QGISin virallisesta repositoriosta, eli se löytyy QGISin lisäosavalikosta. Lisäosan lähdekoodi on julkaistu GitHubissa. Voit lukea lisää työkalun käytöstä ja sen mahdollisuuksista Unfoldedin omille sivuille englanniksi kirjoittamastamme blogikirjoituksesta.

Pienimmän kustannuksen polun määrittäminen perustuu kustannusetäisyystietoa tuottaviin paikkatietoanalyyseihin. Tämä kaksiosainen blogisarja tarkastelee tätä paikkatietoanalyysiä avoimen lähdekoodin työkalujen näkökulmasta, Tässä blogisarjan ensimmäisessä osassa syvennytään hieman aiheen teoriaan ja seuraavassa tarkastellaan ongelmaa ratkovia työkaluja. 

Kustannusetäisyysanalyyseja voidaan soveltaa kaikkiin sellaisiin tilanteisiin, joissa etsittävä reitti on vapaasti muotoiltavissa (ei ole olemassa mitään listaa kohteista, joiden kautta tuloksena saatavan polun tulee välttämättä kulkea). Käytännön esimerkkejä pienimmän kustannuksen polun sovelluskohteista ovat niin maastossa tapahtuvan kulkureitin optimointi, maastoon rakennettavan polkumaisen infrastruktuurin (teiden / voimalinjojen) verkostosuunnittelu kuin eläinten liikkeidenkin mallintaminen. Esimerkiksi kuitukaapelien reititys on yksi käytännön esimerkeistä jossa analyysiä voidaan hyödyntää. Tyypillisesti rasterianalyysi astuu kuvioihin silloin, kun vektorireititykseen tarvittavan topologian muodostaminen osoittautuu liian monimutkaiseksi. Kaikkein yksinkertaisin esimerkki minimikustannuspolkuongelmasta on lyhimmän polun etsiminen pisteestä A pisteeseen B.

Usein kustannuksella viitataan kuitenkin pelkkää etäisyyttä monimutkaisempiin asiakokonaisuuksiin. Sen lisäksi, mikä etäisyys tiettyyn sijaintiin kertyy polun lähtöpisteestä, tiettyyn lokaatioon liitettävään kustannukseen saattaa vaikuttaa myös se, miten paljon rahaa / aikaa / vaivaa ko. lokaatioon pääsemiseen kuluu tai miten paljon negatiivisia ympäristövaikutuksia matkan kulkemisesta kertyy. Esimerkiksi jyrkän mäen kiertävä pyöräilyreitti saattaa kustannuksilla mitattuna osoittautua mäen suoraan ylittävää pyöräreittiä optimaalisemmaksi vaihtoehdoksi.

Minimaalisen kustannuksen tuottavaa polkua ei voida tuottaa ilman tietoa polun ääripisteistä ja siitä, miten kustannus kehittyy liikuttaessa kuhunkin suuntaan. Tämän vuoksi kustannusetäisyysanalyyseissa maailma kuvataan tyypillisesti jatkuvana rasterimuotoisena kustannuspintana, jossa jokaiseen rasterisoluun liittyy positiivinen kustannus. Välitön seuraus tästä on se, että jokainen tämän rasteriavaruuden läpi kulkeva polku kerryttää kustannuksia.

Tässä blogissa tulemme tutustumaan niin vähemmän kuin enemmän tehokkaisiin minimikustannuspolun löytämiseen kehitettyihin avoimen lähdekoodin kustannuspolkualgoritmeihin sekä siihen, millaista aineistoa ne tarvitsevat toimiakseen.

Rakennuspalikat ongelman ratkomiseksi

Optimaalisen minimikustannuspolun tuottaminen koostuu tyypillisesti kolmesta vaiheesta:

1. Kustannuspinnan luominen

• Kustannuspinnan muodostaminen konseptualisoi tutkittavan avaruuden kentäksi
• Kustannuksella viitataan tarkasteltavaan ilmiöön vaikuttavien tekijöiden yhteisvaikutukseen (mittarina käytettävään suureeseen ei yleensä voida liittää mitään järkeenkäypää yksikköä), jonka suuruus voidaan mitata missä tahansa sijainnissa
• Rasteriruudukko luonnissa hyödynnetään usein indeksimalleja ja kartta-algebraa
• Lopputuloksena syntyy kustannustiedon sisältävä rasterimuotoinen ruudukko, jonka jokainen ruutu saa kyseisen ruudun sisällä liikkumisesta aiheutuvaa kustannusta vastaavan arvon

2. Kustannusetäisyystiedon tuottaminen

• Tarvitaan: edellisessä vaiheessa luotu kustannuspinta ja tieto aloituspisteestä
• Kustannusetäisyys kuuluu vaihtoehtoisten etäisyysmetriikoiden perheeseen, sillä sen määrittämisessä hyödynnetään maantieteellistä etäisyyden kitkan -periaatetta, jonka mukaan yksikköliikkeen toteuttamiseen liittyy aina tietty sijainnin mukaan vaihtuvan suuruinen kustannus
• Kustannusetäisyysanalyysissa arvioidaan jatkuvassa avaruudessa tapahtuvan liikkeen kustannusta (muuttujaksi voidaan ajatella kulkeminen tietyn sijainnin kautta)
  • Toisilla poluilla on toisia korkeampi kustannus ja pienempään kustannukseen liittyvää reittiä voidaan aina pitää suuremman kustannuksen tuottavaa polkua parempana valintana
  • Kahden pisteen välinen etäisyys tiettyä polkua pitkin on kerrytetty summa kaikista polun varrelle osuvien pisteiden kustannuksista
  • Tarkoituksena on etsiä pienin painotettu summa kustannuksia, jonka kautta voidaan matkustaa kuhunkin ruutuun aloitusruudusta (etäisyyttä mitataan maantieteellisten yksiköiden sijaan kustannusyksiköissä)
• Lopputuloksena syntyy kustannusetäisyystiedon sisältävä rasterimuotoinen ruudukko, jonka jokainen ruutu sisältää kyseiseen lokaatioon pääsemiseksi kertyvän kustannuksen
  • Käytännössä tämä arvo saadaan selville erkanemalla säteittäin lähtöpisteestä ja tunnistamalla pienimmän kerrytetyn kustannuksen omaavan naapuriruudun ja lisäämällä sen kerrytetty kustannus tarkasteltavan ruudun kustannukseen (diagonaalisten pienimmän kustannuksen naapuriruutujen tapauksessa käytetään kertoimena kakkosen neliöjuurta)

• Kerrytetyn kustannusetäisyysruudukon lisäksi tuotetaan myös toinen, erillinen ruudukko (backlink rasteritiedosto), johon talletetaan tieto suunnasta, mistä löytyy kunkin ruudun pienimmän kerrytetyn kustannuksen omaava naapuriruutu
  • Toisin sanoen tallennetaan tieto siitä, mistä suunnasta pienimmän kustannuksen polku tulee kuhunkin ruutuun

3. Pienimmän kustannuksen tuottavan polun löytäminen

• Tarvitaan: edellisessä vaiheessa luotu backlink rasteri ja tieto polun päätepisteistä
• Toimintaperiaate: algoritmi tunnistaa päätepisteeseen liittyvän backlink rasterin ruudun ja jäljittää polun päätepisteestä takaisin aloituspisteeseen liikkumalla kustakin ruudusta, johon ollaan saavuttu peruutuksen seurauksena, aina pienimmän kerrytetyn kustannuksen omaavaan naapuriruutuun
  • Jokaista läpi peruutettua ruutua vastaava kustannus saadaan selville vaiheessa 2 muodostetusta kerrytetyn kustannusetäisyyden ruudukosta (näistä tiedoista lasketaan optimaalisen polun kokonaiskustannus)

Seuraavassa blogisarjan osassa päästään itse asiaan – eli syventymään erilaisiin keinoihin määrittää minimikustannuspolku!

QGISin attribuuttilomakkeiden muotoilutoiminto helpottaa arkista paikkatietotyöskentelyä huomattavasti. QGISin työtilan tasojen ominaisuustietolomaketta voi nimittäin kustomoida omiin tarkoituksiin todella helposti. Muille voit kehua koodanneesi QGISiin uuden lisäosan, jolla tietoja jatkossa hallitaan. 

Lomakenäkymä voi olla perinteistä taulukkonäkymää mukavampi käyttää esimerkiksi kohteita digitoitaessa tai jos halutaan saada aineistosta näkyviin vain tiettyjä asioita. Myös kalenterinäkymä päivämäärätyyppisissä kentissä tai kuvamuotoisen linkin esittäminen lomakkeella voi olla kätevää.

Valitse ensin vektoriaineisto, jolle haluat tehdä lomakkeen. Huomaathan, että tekemäsi muutokset tallentuvat vain QGIS-projektiin eli muista tallentaa projekti aina lomakkeen muokkauksen jälkeen. 

Klikkaamalla auki tason Ominaisuudet / Layer Properties -näkymän ja sieltä Attribuuttilomake, pääset muokkaamaan attribuuttitaulujen esitystapaa. 

Automaattisessa näkymässä lomake näyttää kaikki kentät, joita aineisto sisältää sellaisenaan. Klikkaamalla auki ylävalikosta “Automaattinen” sijaan “Drag and Drop Designer”-näkymän, jolloin voit tehdä mm. seuraavaa:

• Klikata pois näkyvistä ne kentät, joita et tarvitse (esim. Fid-kenttä, joka generoituu automaattisesti)
• Voit antaa sarakkeille aliasnimen, joka kuvaa kenttää paremmin
• Widgetin avulla voidaan myös antaa saraketyypille lisäominaisuuksia, kuten alasvetovalikon, josta käyttäjä saa valita vain tiettyjä arvoja (arvoluettelo). 
• Tai voit luoda lomakkeelle välilehtiä tai järjestellä kenttiä haluamallasi tavalla

Tässä esimerkissä “korkeus”-kenttään luodaan arvolista, jossa voi antaa vain 5 m välein arvoja. Arvoluettelon voi tuoda myös toisesta aineistosta tai csv-tiedostosta, jos halutaan käyttää olemassaolevaa koodilistaa. 

Kun jatkossa luot kohteita tai klikkaat ne auki info-näppäimellä, avautuu muotoiltu lomake näkyviin. Lomake näyttää siis vain valitut kentät ja niiden aliasnimet, sekä helpottaa tietojen syöttöä esimerkiksi alasvetovalikkojen avulla.

Päivämäärämuotoinen (date)-kenttä näyttäytyy myös heti kalenterimerkintänä. 

Jos haluat viedä lomakenäkymiä askeleen pidemmälle, voidaan ottaa käyttöön myös välilehdet tai palstajako, joiden avulla voidaan iso määrä attribuutteja esittää ryhminä. 

Kuvan kaltaisen toteutuksen saa tehtyä attribuuttilomakkeen drag & drop-asettelusta luomalla Taitto-näkymään yläotsikoita tab-muotoisena (välilehti) tai ryhmitellä attribuuttien kenttiä allekkain (ryhmä säiliössä). Myös palstoitukseen voi vaikuttaa lisäämällä sarakkeiden lukumäärää.

PostGIS-tietokanta ja sen relaatiomahdollisuudet tuovat vielä yhden lisäherkun QGISin lomakkeisiin. Tässä esimerkissä on taustalla PostGIS-tietokanta, jossa paikkatietokohteeseen liittyy tekstimuotoisesta taulukosta tietoja. Lomakenäkymää muokkaamalla saa ensinnäkin raahattua lomakkeelle oikean relaation ja sen jälkeen voidaan määrittää saako käyttäjä lisätä lomakenäkymän kautta uusia rivejä kyseiseen taulukkoon vai ei. Relaatioita voi toki hyödyntää ilman PostGISiäkin, esim. GeoPackagen avulla. Relaatioiden tuottamisesta olemme kirjoittaneet aiemmin. 

Eli sitten vaan lomakkeet kuntoon ja tehokkuutta tietojen tuottamiseen!

Lisäluettavaa tästä löytyy mm. QGISin ohjesivuilla sekä koulutamme myös aiheeseen.

Pääsin mukaan mentoriksi Planin ja Future Femalen järjestämään nuorten teknologiavaikuttajien kampanjaan, jossa yhdessä Tieken toiminnanjohtajan Hanna Niemi-Hugaertsin kanssa koitamme parhaamme mukaan antaa työelämän vinkkejä ihanalle nuorten ryhmälle.

Hannan kanssa yhteinen taival alkoi vuonna 2015, kun teimme töitä 6Aika avoin data -kärkihankkeessa ja pohdimme yhdessä miten ja mitä dataa kaupungeissa avataan. Siksi ryhmämme aiheena on kaupunkidata – joka yhdistää paikkatiedot, avoimen datan, my datan ja IoT-asiat käteväksi paketiksi. Nuorten kanssa pohdimme siis yhdessä mitä voisimme tehdä, jotta kaupungeista ei tulisi ihan älyttömiä ja miten he voivat jo nyt teoillaan vaikuttaa tasa-arvokysymyksiin ja samalla tulevaisuuden teknologioiden kehittämiseen. Kevään aikana ryhmä tuottaa jonkin vaikuttamistoimenpiteen ja jännityksellä odotan mitä saamme aikaan!

Lauantaina oli kickoff Planin ja Future Femalen kanssa ja tutustuimme mm. juuri tasa-arvoasioihin ja itse vähän jopa järkytyin siitä, että Suomessa on esimerkiksi edelleen IT-alan työntekijöistä 80 % miehiä. Ja vielä kamalampaa oli kuulla, että 45 % tytöistä kokee nettihäirintää eli melkein joka toinen kadulla kävelevä nainen on kokenut verkkohäirintää!  Tällaiset asiat kuuluvatkin niihin älyttömiin kaupunkeihin, joissa kukaan meistä ei halua elää. 

Paikkatietoalalla tasa-arvoasiat ovat suht hyvällä mallilla, mutta huomaan kyllä esimerkiksi rekrytointitilanteissa, että teknisemmin orientoituneita hakijoista on järjestäen pääosa miehiä. Esimerkiksi FOSS4G 2019 tapahtumassa Bukarestissa oli hienosti järjestetty tytöille oma sosiaalinen tapahtuma, joka joillekin oli ainoa tilaisuus päästä minglailemaan ja juttelemaan alan kehityksestä, sillä muuten he eivät kulttuurisista tai uskonnollisista syistä voineet osallistua tapahtumiin. Se oli itselle heräte siihen, että vielä on paljon tehtävää. Me suomalaiset paikkatietomuijat voidaan osaltaan myös näyttää mallia niin kotona kuin maailmalla. 

Meillä Gispolla toivon, että tasa-arvosasiat näkyisivät kaikessa tekemisessä – meitä on melkein fifty-fifty naisia ja miehiä – tosin jokainen rekrytointi kallistaa aina kuppia puoleen ja toiseen. Mutta täysin tasa-arvoiseksi ja heterogeeniseksi sakiksi en voi meitä vielä hyvällä omatunnolla kutsua. Me kaikki olemme tällä hetkellä korkeakoulutettuja valkoisia 25-50-vuotiaita kantasuomalaisia. Se miksi meillä ei ole esimerkiksi muita kuin suomea pääkielenään puhuvia, johtuu pitkälti asiakaskeisseistä ja aineistoista, joita käytämme. Asian ei toki tarvitsisi olla näin. 

Naistenpäivän kunniaksi toivotankin kaikille tasa-arvoista kevättä – otetaan toisemme huomioon, mietitään asioita myös sen toisen kantilta ja pohditaan miten voidaan ottaa myös teknologiassa tasa-arvoasiat huomioon ja vaikuttaa siihen, että asiat paranevat. Niin aion itse tehdä myös ja tämän kevään mentorointitehtävä on mahtava tilaisuus tehdä jotain konkreettista. Kiitos siitä Hanna ja Planin ja Future Femalen posse! 

Parhaimmassa tapauksessa reittioptimoinnilla kyetään vastaamaan jokaiseen otsikossa esitetyistä kysymyksistä. Tässä blogissa pääset tutustumaan niin reittioptimoinnin, mallinnuksen, graafien, QGISin, PostGISin, CPLEXin kuin yleisen (ohjelmointi)logiikankin maailmoihin – lukuiloa!

Johdanto

Matemaattista optimointia voi osuvimmin kuvata parhaan ratkaisun etsimiseksi olemassaolevien vaihtoehtojen joukosta. Tyypillisesti etsitään sellaista ratkaisua, joka minimoi / maksimoi kohdefunktioksi kutsuttavan, vaihtoehtojen paremmuutta vertaavan kriteerin arvon. Optimoitavaa suuretta kutsutaan päätösmuuttujaksi. Päätösmuuttujien arvoja muuttamalla pyritään saavuttamaan mahdollisimman hyvin asetetun optimointiongelman tavoitteet. Optimointiongelman tavoitetta kutsutaan kohdefunktioksi. Kohdefunktiot koostuvat päätösmuuttujista, parametreista, vakioista sekä niiden välisistä relaatioista. Parametrien voidaan ajatella kuvaavan kyseessä olevan systeemin ominaisuuksia. Vakiot puolestaan voidaan nähdä parametreja muuttumattomampina, universaaleina ominaisuuksina.

Optimointimallia muodostettaessa tulee ottaa kohdefunktion lisäksi huomioon myös päätöksiä rajoittavat ehdot. Tällaisia ehtoja kutsutaan rajoitteiksi. Usein malleihin liittyy luonnollisia rajarajoitteita, jotka aiheutuvat päätösmuuttujalla kuvattavan suureen ominaisuuksista. Jos esimerkiksi yritetään minimoida aikaa, joka romaanin kirjoittamiseen tulee kulumaan, päivässä käytettävien työtuntien määrää kuvaavalle päätösmuuttujalle x täytyy asettaa alaraja x ≥ 0. Vuorokaudessa ei nimittäin ole mahdollista työskennellä negatiivista määrää tunteja. Rajoitefunktioiden avulla voidaan kuvata monimutkaisempia rajoitteita. Esimerkkinä tällaisesta voisi toimia vaikkapa rajoite, joka vaatii, että jokaista vuorokaudessa työskenneltävää kolmea tuntia kohti täytyy pitää yksi kahvitunti, nukkumiseen täytyy varata ainakin kuusi tuntia, ja näiden kolmen päätösmuuttujan summa ei saa ylittää 24 tuntia. Kahvitunnin pitämisestä ja nukkumisesta saatava hyöty voidaan kuvata kohdefunktiossa päätösmuuttujien välisenä relaationa. Kyseiseen relaatioon voi liittyä sekä parametrejä että vakioita, joiden avulla pystytään kuvaamaan monimutkaisempia vuorovaikutussuhteita.

Merkitään symbolilla N optimointimalliin liittyvien päätösmuuttujien lukumäärää. Mikäli päätösmuuttujien arvoista koostuva N-ulotteinen vektori toteuttaa kaikki optimointimallin rajoitteet, ollaan löydetty sallittu ratkaisu. Minimointi-tyyppisen optimointiongelman optimaaliseksi ratkaisuksi kutsutaan sellaista sallittua pistettä, jossa kohdefunktio saa pienimmän arvonsa.

Reittioptimointi on eräs optimoinnin alakategorioista. Reittioptimointi voidaan nähdä tieteenalana, jonka tavoitteena on löytää systemaattisia tapoja tunnistaa nopein / kustannustehokkain tapa järjestää jonkin resurssin kuljetus. Reittioptimoinnin keinoin voidaan reititysratkaisujen etsimisen lisäksi pyrkiä vastaamaan myös laajempiin yritysmaailman tavoitteisiin (esim. parantamaan asiakastyytyväisyyttä, vähentämään toiminnan kustannuksia tai optimoimaan työsuunnittelua). Yksi perinteisimmistä reittioptimoinnin ongelmista on Kauppamatkustajan ongelma (Travellling Salesman Problem), jossa tavoitteena on löytää pienimmän kustannuksen omaava reitti, joka kulkee usean kaupungin / kohteen kautta ja palaa takaisin lähtöpisteen [4]. Tässä blogissa tulemme kuitenkin etsimään vastausta hieman erityyppiseen reittioptimointi-ongelmaan, jota pääsimme tutkimaan yhteistyössä Tampereen Infra Oy:n kanssa.

Aurausongelman mallinnus

Toteutuneen hankkeen aikana tutkittiin monia tapoja mallintaa aura-auton ajoreitin valitsemiseen liittyvää problematiikkaa. Reittioptimointi yhdessä mielessä hyvin erityinen analysointitapa; on aivan samantekevää onko meillä käytettävissä aineistoa esimerkiksi aura-autojen liikkeistä. Sillä, miten asia on tavattu tehdä, ei ole juurikaan vaikutusta siihen, miten se oikeasti kannattaisi tehdä. Tässä työssä hyödynnettiin lähtöaineistoina ainoastaan Digiroadin tarjoamaa tieverkostodataa, tarkasteltavan alueen määrittävää aluerajausta ja tietoa kunnossapitoajoneuvojen varikon sijainnista. Haasteelliseksi optimoinnin tekee se, että tutkittava ilmiö onnistutaan mallintamaan realistisesti. Optimointi on aina tasapainoilua kehitetyn mallin validiteetin ja ratkeavuuden välillä.

Ihan ensimmäiseksi muokkasimme Digiroadin tieverkkoaineiston sellaiseen muotoon, jonka päälle pystytään rakentamaan matemaattinen ongelmanmuotoilu. Toisin sanoen loimme PostGIS:n avulla todellisesta tieverkosta topologisesti ehjän graafin. Graafi on verkosto, joka koostuu solmuista (kuvaavat tässä tapauksessa teiden risteyksiä) ja niitä yhdistävistä kaarista (vastaavat teitä). Graafit jaotellaan luokkiin niiden ominaisuuksien mukaan. Tärkeimmät graafeja määrittävät ominaisuudet liittyvät siihen, onko graafi suunnattu (jokaiseen kaareen liittyy suuntatieto → yksi lähtösolmu, yksi päätesolmu), kytketty (jokaiselle solmuparille (a,b) on olemassa yhtenäinen polku solmusta a solmuun b) tai painotettu (jokaiseen kaareen liittyy painokerroin, yksinkertaisimmillaan kaaren pituus).

Tavanomaisimmat graafiteorian mallit, kuten aiemmin mainittu kauppamatkustajaongelma, perustuvat ajatukselle, että tavoitteena on käydä jokaisessa graafin solmussa. Tämä tavoite ei kuitenkaan sovellu kunnossapidon tavoitteisiin, sillä solmuissa käymisen sijaan tavoitteena on kulkea jokainen kaari. Käsillä olevan ongelman mallintamiseen soveltui paremmin Chinese Postman Problem (CPP), jonka periaatteet voidaan tiivistää seuraavasti:

• Postimiehen tavoitteena on jakaa kaikki alueen postit kulkien mahdollisimman lyhyttä reittiä
• Kyetäkseen tekemään tämän, hänen tulee kulkea jokainen tienpätkä vähintään kertaalleen ja palata sen jälkeen lähtöpisteeseen
• Mikäli CPP saadaan ratkaistua, tuloksena saatua polkua voidaan pitää optimaalisena tapana kiertää tieverkosto (turhien ajokilometrien määrä minimoituu)

Yllä esitellyssä CPP-muotoilussa on kuitenkin yksi iso ongelma, joka asettaa koko mallin validiteetin kyseenalaiseksi: siinä kaikki tiet ymmärretään samanlaisiksi, kahta risteystä yhdistäväksi suuntaamattomaksi kaareksi. Toisin sanoen, perus-CPP:n avulla ei ole mahdollista ottaa huomioon ajosuuntaa ja sitä, että on olemassa sekä yksisuuntaisia että kaksisuuntaisia teitä. Siksipä hankkeessa kehitettiinkin muokattu versio CPP kokonaislukuoptimointiongelmasta, jonka periaatteet voidaan tiivistää seuraavasti:

1. Minimoidaan kuljettavaa matkaa
2. Jokaiseen tienpätkään liittyy yksi kokonaislukumuuttuja, joka kuvaa montako kertaa kyseinen tiepätkä optimaalisessa ratkaisussa kannattaisi ajaa
3. Jokainen kaksisuuntainen tie tulee kulkea kuhunkin suuntaan vähintään kertaalleen
4. Jokainen yksisuuntainen tie tulee kulkea sallittuun kulkusuuntaan vähintään kahdesti
5. Aura-auton tulee lähteä varikolta ja optimaalisen reitin tulee päättyä varikolle
6. Ratkaisuna saatavan optimaalisen polun tulee olla topologisesti ehjä (jokaisessa tieverkon risteyskohdassa tulee olla tasapainoehto voimassa)

Aurausongelman muodostus

Ongelman ratkaisuprosessi sisälsi seuraavat vaiheet:

1. Aineiston esikäsittely QGISillä

• Leikkaa Digiroad-aineistoa (DR_LINKKI_K) tutkittavan alueen määrittävällä aluerajauksella
• Muokkaa tarvittaessa aluerajauksen reunoja siten, ettei se katkaise yhtään tiesegmenttiä “keskeltä”
• Luo uusi tiesegmentti lähtöpisteestä lähimpään tiehen (jos sitä ei ole vielä olemassa)
• Tarkista, ettei leikkauksen tuloksena saatu verkosto sisällä multiedgejä (tilanne, jossa samaa pisteparia yhdistä kaksi eri tiesegmenttiä). Käytännössä tällainen tilanne voi muodostua “kaariteiden” yhteydessä
• Tarkista, ettei yksisuuntaisia teitä ole verkoston reunoilla (ulos alueelta / sisään alueelle), koska siellä ei tällöin voitaisi käydä kääntymässä → mahdotonta löytää topologisesti ehjää aurauspolkua

2. Graafin muodostaminen PostGISin pg_routing-laajennuksen avulla

• Luo PostGISiin tietokantaklusteri ja tietokanta (esim. pgAdminilla), jonne voit viedä tarkastelualueen tieverkoston

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

• Vie esikäsitelty tieaineisto PostGISiin

ogr2ogr -update -append -a_srs EPSG:3067 -nlt LINESTRING -lco GEOMETRY_NAME=geom -lco FID=id -lco SCHEMA=reititys -f PostgreSQL "PG:host= port= user= dbname= password=" -nln reititys.tietPgis tietQgis.gpkg

3. Tiedon jalostaminen

ALTER TABLE reititys.tietPgis
ALTER COLUMN geom TYPE geometry(LineString,3067)
USING ST_Force2D(geom);
ALTER TABLE reititys.tietPgis
ADD COLUMN source integer;
ALTER TABLE reititys.tietPgis
ADD COLUMN target integer;
SELECT pgr_createTopology('reititys.tietPgis',0.0001,'geom','id');
ALTER TABLE reititys.tietPgis
ADD COLUMN pituus float;
UDATE reititys.tietPgis
SET pituus = ST_Length(geom);

• Luodaan uusi PostGIS-taulu, johon tallennetaan vain tarvittavat tiedot tienpätkistä

CREATE TABLE reititys.tiet(
id BIGSERIAL,
ajosuunta BIGINT,
source BIGINT,
target BIGINT,
pituus FLOAT,
geom text,
temp1 BIGINT,
temp2 BIGINT);

INSERT INTO reititys.tiet(
id, ajosuunta, source, target, pituus, geom, temp1,temp2)
select id, ajosuunta, source, target, pituus, ST_AsText(geom), source, target
from reititys.tietPgis;

• Lisätään tauluun sarake, joka sisältää tiedon siitä, mihin tiesegmenttiin kukin tienpätkä liittyy

ALTER TABLE reititys.tiet
ADD COLUMN tieid float;
UPDATE reititys.tiet
SET tieid = id;

• Lisätään jokaista kaksisuuntaista kaarta kohti myös digitointisuunnan suhteen vastainen rivi

INSERT INTO reititys.tiet(
id, ajosuunta, source, target, pituus, geom, temp1, temp2, tieid)
select id+kaarien_lkm, ajosuunta, source, target, pituus, ST_AsText(geom), source, target, id
from reititys.tietPgis
where ajosuunta=2;

• Muokataan näille lisätyille riveille source ja target toisinpäin

UPDATE reititys.tiet
SET source = temp2,
target = temp1
where id > kaarien_lkm;

• Muokataan digitointisuunnan vastaisesti tallennettujen kaarien osalta source ja target tiedot oikein päin

UPDATE reititys.tiet
SET source = temp2,
target = temp1
where ajosuunta = 3;

• Korvataan ajosuunnat 3 / 4 arvolla 1, joka kertoo, että kyseessä on yksisuuntainen tie

UPDATE reititys.tiet
SET ajosuunta = 1
where ajosuunta = 3 or ajosuunta = 4;

• Viedään luodut tiedot pois PostGISista csv-tiedostoina psql avulla

\copy (select * from reititys.tiet order by id) TO '/tiet2.csv' CSV HEADER
\copy (select id, ST_AsText(the_geom) from reititys.tiet_vertices_pgr order by id) TO '/solmut.csv' CSV HEADER

4. Optimointiongelman muodostaminen

Edellisessä vaiheessa luodut csv-tiedostot pitävät sisällään kaiken tiedon, jota tarvitset optimointiongelman muodostamiseen (tiedon jokaisen tienpätkän lähtösolmusta, päätesolmusta ja painokertoimena toimivasta pituudesta).

Leluesimerkki:

minimize pituus1 x1+pituus2 x2+pituus3 x3+...+pituusN xN
subject to

• Solmusta A lähteviin tienpätkiin liittyvät päätösmuuttujat – solmuun A päättyviin tienpätkiin liittyvät päätösmuuttujat = 0:

x2-x1-x4=0
x1-x3=0
...
bounds

• Yksisuuntaiseen tiehen liittyville päätösmuuttujille:

x1<=2

• Kaksisuuntaiseen tiehen liittyville päätösmuuttujille:

x2<=1
x3<=1
...
xN<=1
integer
x1
...
xN
end

• Huomaa, että tasapainoehtoja (subject to -osio) tulee yksi jokaista graafin solmua kohti ja rajarajoitteita (bounds-osio) yksi kutakin graafin kaarta kohti
• Huomaa myös, että tässä leluesimerkissä pituus1=pituus2, sillä päätösmuuttujat x1 ja x2 ovat saman tien kaksi vastakkaissuuntaista pätkää
• Optimointiongelman muodostaminen kannattaa automatisoida esimerkiksi luomalla lyhyt python skripti, joka hyödyntää csv-tiedostojen sisältöjä ja kirjoittaa niiden pohjalta optimointiongelman formuloinnin leluesimerkin mukaisessa muodossa tekstitiedostoon
  • LP-tiedoston luomiseen liittyy omat avainsanansa ja oma syntaksinsa [2]
• Lopuksi tulostiedostosta (optongelma.txt) tulee ottaa kopio ja tallentaa se .lp-muodossa

Optimointiongelman ratkaiseminen

CPLEX on lineaaristen ja rajoitteellisten kokonaislukuoptimointiongelmien ratkaisemiseen soveltuva ohjelmisto. CPLEX-ohjelmisto on IBM ILOG:n akateemisiin tarkoituksiin avoimesti ladattavissa oleva optimointiohjelmistopaketti, joka koostuu algoritmeista, työkaluista ja rajapinnoista. Koska kokonaislukuoptimointitehtävien ratkaisemiseen ei ole olemassa yhtä ylivertaisen tehokasta algoritmia, CPLEX-ohjelmistokin sisältää useita vaihtoehtoisia optimointitekniikoita. Ohjelmisto osaa itse valita kuhunkin tilanteeseen parhaiten soveltuvan ratkaisumenetelmän. Kokonaislukumuuttujia sisältäviin optimointiongelmiin soveltuvia eksakteja (takaavat ratkaisun optimaalisuuden) menetelmiä ovat CPLEX-ohjelmiston optimoijista muun muassa Branch and Cut -menetelmä ja dynaamisen etsimisen menetelmä. CPLEX pystyy lukemaan ratkaistavana olevan optimointiongelman suoraan komentorivin kautta lp-tiedoston muodossa tallennetusta tekstitiedostosta:

read 

Itse optimointitehtävän ratkaisu onnistuu yhdellä käskyllä:

optimize

Optimaaliset päätösmuuttujan arvot saa näkyviin syöttämällä CPLEX:n komentoriville:

display solution variables *

• CPLEX on todella tehokas tämän tyyppisten ongelmien ratkaisemisessa; yli 900 päätösmuuttujan ongelman ratkaisemiseen meni alle puoli sekuntia

Ratkaisusta käy ilmi, että optimaalinen reitti, joka kulkee jokaisen tutkitun alueen tien kautta optimointiongelman rajoitteet täyttäen, on 58.9 kilometriä pitkä. Kyseessä on ehdoton alaraja sille, kuinka monta kilometriä vähintään täytyy ajaa, jotta alueen tiet saadaan käytyä läpi. Tätä alarajatietoa voi hyödyntää esimerkiksi arvioitaessa alueen läpikäymiseen varattavan polttoaineen tai sepelin määrää.

Kuvassa 1 on visualisoitu optimaalisen ratkaisun ajokerrat. Ensinnäkin on hieman yllättävää, että suurin osa kaksisuuntaisista teistä pystyttäisiin periaatteessa ajamaan vain kertaalleen molempiin suuntiin. Se taas on täysin odotettua, että yksisuuntaisia teitä ei kannata ajaa kuin minimimäärä eli kahdesti kulkusuuntaan (havainnollistettu nuolella). Mielenkiintoisin osa ratkaisua lienee se, että kuvasta nähdään mitä teitä pitkin kannattaa reitin kokonaismatkan minimoinnin kannalta kulkea ne pakolliset kierrokset, jotka välttämättä joudutaan suorittamaan, jotta verkoston jokainen kaksisuuntainen tie voidaan kulkea vähintään kerran molempiin suuntiin ja jokainen yksisuuntainen tie voidaan kulkea topologisesti ehjää reittiä pitkin vähintään kahdesti rikkomatta liikennesääntöjä.

Kiertojärjestyksen määrääminen optimaalisen ratkaisun pohjalta

Huolimatta siitä, että kokonaislukuoptimointiongelmaan on jo saatu määritettyä “ratkaisu”, emme silti vielä pysty vastaamaan otsikossa esitettyyn mistä, minne ja miten -kysymykseen. Pystyäksemme vastaamaan tähän kysymykseen, meidän on vielä selvitettävä missä järjestyksessä aura-auton tulee tieverkkoa kuvaavan graafin solmuissa käydä, jotta aura-auto pystyy lähtemään varikolta ja palaamaan sinne siten, että aura-auto on kulkenut läpi koko tieverkkoa vastaavan graafin ajamalla kutakin tienpätkää täsmälleen niin monta kertaa kuin CPLEXillä löydetty optimaalinen ratkaisu ohjeistaa.

Ajojärjestyksen määräämiseen kehitettiin toinen python skripti. Tämä python ohjelma tarvitsee kuitenkin toimiakseen huomattavan määrän valmiita “aliratkaisuja”. Python ohjelman logiikka on seuraava:

1. Hyödynnetään CPP ongelman ratkaisemiseen kehitettyä kokeellista QGIS pluginia Chinese Postman Solver
2. Tarkastellaan pluginin palauttamaa ratkaisua karttapohjalla ja jaetaan tarkasteltava verkosto alialueisiin sen mukaan, että jokainen alialue sisältää yhden yhtenäisen, pluginin palauttamassa ratkaisussa vain kertaalleen toiseen suuntaan kuljettavan polun, josta poiketaan muille teille vain edestakaisilla pistoilla
3. Tallennetaan alialueet omiksi karttatasoikseen ja valitaan “porttisolmut”, joiden kautta siirrytään alialueelta toiselle (tämä solmu voi olla mikä tahansa kahta alialuetta yhdistävä edestakaisen “pistotien”solmu) 

• Samalla tulee miettiä järkevä järjestys edetä alialueelta toiselle (tärkeää, että polku “sisimpään” alialueeseen kulkee kaikkien muiden alialueiden kautta)

4. Ratkaistaan CPP ongelma uudelleen jokaiselle alialueelle em. QGIS pluginin avulla

• Tuloksena saadaan lista tieverkoston solmujen ID:itä, joka määrittää optimaalisen kiertojärjestyksen alialueelle

5. Luodaan python skripti, joka noudattaa näitä alialueiden optimaalisia ratkaisupolkuja siihen asti, että kyseinen ratkaisupolku kulkee jonkin toisen alueen porttisolmun kautta → edetään suorittamaan seuraavan alialueen ratkaisupolkua
6. Edetään eteenpäin verkostossa aina siihen asti, että päädytään sisimmän alialueen yhtenäisen polun päähän

• Tämän jälkeen lähdetään peruuttamaan yhtenäistä polkua takaisin päin aina siihen asti kunnes palataan sisimmän alialueen porttisolmulle
• Porttisolmulle palaamisen jälkeen jatketaan toiseksi sisimmän alialueen optimaalisen ratkaisupolun suorittamista, kunnes päädytään kyseisen alialueen ratkaisupolun päähän → aletaan jälleen peruuttaa kohti toiseksi ja kolmanneksi sisimmän alialueen välistä porttisolmua
• Tällä logiikalla palaamme lopulta takaisin varikolle siten, että jokaista verkoston tienpätkää on kuljettu kertaalleen molempiin kulkusuuntiin

Kuten tarkkasilmäisimmät saattoivat huomatakin, edellä mainittu logiikka perustuu ajatukselle, että jokaista tietä tulisi kulkea tasan kerran molempiin suuntiin. Jo pelkästään ongelmanmuotoilu (yksisuuntaisten teiden huomioonottaminen) määrittää, ettei tällaista oletusta voida tehdä. Lisäksi tiedämme CPLEXin tuottaman ratkaisun perusteella, että osaa kaksisuuntaisista teistä joudutaan ajamaan useamman kerran toiseen kulkusuuntaan. Syy, miksi voimme hyödyntää kiertojärjestyksen määräämisessä yllä kuvatun kaltaista logiikkaa on se, että eristimme tieverkostograafista ensin ne tienpätkät, joille ei päde se, että optimaalisessa ratkaisussa ko. tiesegmentti tulisi ajaa täsmälleen kerran molempiin kulkusuuntiin.

Tästä saatiin ensimmäinen alialue, jonka optimaalinen kiertojärjestys määrättiin manuaalisesti karttapohjaa katsomalla ja miettimällä minne seuraavaksi etenemällä pystyn kiertämään kaikki tiet täsmälleen niin monesti kuin optimaalinen ratkaisu ohjeistaa. Myös tälle “looppialueelle” määritettiin porttisolmu vastaavalla tavalla kuin muille alialueille, ja python skriptin näkökulmasta se oli samanlainen alialue kuin kaikki muutkin. Ainoa ero on se, että looppialueen ratkaisupolun tuottamiseen ei voitu hyödyntää QGIS pluginia, vaan se määritettiin loogisen päättelyn avulla.

Prosessiputken rakentamisen kannalta oli keskeistä oivaltaa, että looppialue kannattaa eristää ja että sille voidaan loogisesti päätellä järkevä kiertojärjestys. Ensinnäkin tämä mahdollisti kiertojärjestyksen ongelman redusoitumisen sen kokoiseksi, että ihmisaivot pystyivät looppialueen ratkaisujärjestyksen määrittämään. Toisekseen tällä tavalla saimme ensiarvoisen tärkeää tietoa siitä, miten moni asia vaikuttaa kiertojärjestyksen määräytymiseen. Kolmanneksi saimme muun tutkimusalueen muovattua sellaiseen muotoon, joka on hyvin lähellä perus-CPP:n ongelmanmuotoilua. Toki me tiesimme CPLEXin ratkaisun perusteella jo, että jokainen tie tulisi kulkea edestakaisin ja tätä ei perus-CPP:ssä vaadita. Kuitenkin, perus-CPP:ssä vaaditaan, että jokainen tie kuljetaan läpi ainakin kertaalleen. Todennäköisesti siis pystyisimme pluginilla tuottamaan sellaisen ratkaisun tälle verkoston loppuosalle, josta saisimme selville jotain hyödyllistä. Osa teistä varmasti tulisi pluginin ratkaisussa käytyä edestakaisesti, jolloin ratkaisu olisi näiden osalta jo valmis. Ja vaikka osa teistä käytäisiin vain kertaalleen läpi, eikö olisi mahdollista kulkea tällainen yhtenäinen polku (matkalle osuvissa “pussinperissä” poiketen) aluesta loppuun asti ja peruuttaa sitten takaisin, jolloin kaikki tiet tulisi ajettua täsmälleen kerran molempiin kulkusuuntiin?

Suoritettuani pluginin koko “ykkösverkostolle” (koko verkosto – looppialue), havaitsin, että saatu ratkaisu oli pitkälti toivomani kaltainen. Ainoana isona ongelmana näytti olevan se, ettei tällaista yhtä yhtenäistä yhden kulkusuunnan polkua näyttänyt muodostuvan, vaan niitä oli muodostunut useita ympäri ykkösverkostoa. Niinpä päätin rajata ykkösverkoston alialueisiin sen mukaan, että jokainen alialue sisältää täsmälleen yhden tällaisen yhtenäisen yhteen suuntaan pluginin ratkaisussa kuljettavan polun + kasan pussinperäksi luokiteltavia visiittejä sivuteille. Tarve uuden alialueen muodostamiselle syntyi siis aina, kun yhtenäinen polku katkesi tiellä, joka pluginin ratkaisussa haluttiin ajaa edestakaisin.

Python skriptiin ohjelmoitiin myös tarkistusproseduuri siltä varalta, ettei plugin ole kaikilta osin tehnyt samoja valintoja kuin CPLEXillä tuotettu optimaalinen ratkaisu edellyttäisi. Jos näin on, joitakin tienpätkiä jää kulkematta. Tällaiset tilanteet ratkottiin manuaalisesti katsomalla karttapohjasta, että tässä kohtaa ollaan toisen kerran käytetty samaa kaarta, mutta samat solmut voi yhdistää myös kiertämällä useampia solmuja pitkin (nämä ovat juuri niitä solmuja, jotka ovat jääneet kulkematta). Kaiken kaikkiaan voisi sanoa, että osittamalla ongelma järkevällä tavalla alialueisiin, päästiin niin lähelle, että perus-CPP:n ratkaisemiseen kykenevää QGIS pluginia hyödyntämällä pystyttiin päättelemään loput ja löytämään kiertojärjestys, joka noudattaa täsmälleen CPLEXillä määrätyn optimaalisen ratkaisun ajokertoja.

Lopputulos

On ilmeistä, että skaalautuvuus on kehitetyn prosessiputken haaste. Tieverkoston graafin rakentaminen ja optimointiongelman ratkaiseminen on nopeaa, kiertojärjestyksen määrääminen taas monilta osin manuaalista ja virhealtista. Hyvä puoli kehitetyssä menetelmässä on, että se mallintaa ongelman realistisesti, löydetyn ratkaisun optimaalisuus on taattu ja ratkaisu on otettavissa käyttöön sellaisenaan. Ratkaisu määrittää suoran toimintaohjeen, joka on validi niin pitkään, kun tieverkkoon ei tule muutoksia.

Alla olevista videoista näet, miten Tampereen Pispalan kadut kannattaisi aurata. Ratkaisusta käy ilmi, että toteuttamalla reittioptimointi edellä kuvatun prosessiputken kautta on mahdollista vastata kysymykseen, miten jonkin alueen tiet kannattaisi ajaa läpi, jos halutaan minimoida aura-auton ajamaan kokonaismatkaa. Tavoite ajoreitin kokonaispituuden minimoinnista on perusteltu, sillä tällöin ajoaika ja sitä kautta ilmakehään päätyvät päästötkin minimoituvat.

Valitettavasti projektin aikana tuotettua tulosta ei voitu suoraan ottaa käyttöön. Digiroad-aineiston sisältövirheiden vuoksi muutama portaikko oli digitoitu teiksi, joita pitkin optimaaliset aurauspolutkin sitten kulkivat. Huolimatta harmittavasta takaiskusta, projektissa onnistuttiin luomaan prosessiputki, jonka avulla todellisesta tieverkosta (virheineen) voidaan luoda graafi, jolle voidaan luoda muokattu reaalimaailman ongelmaa todenmukaisesti mallintava optimointiongelma, joka kyetään ratkaisemaan ja jonka ratkaisu kyetään muuntamaan niin suoraksi toimintaohjeeksi, että siitä voidaan muutamassa minuutissa nähdä, mitä ratkaisu käytännössä ehdottaa. Valitettavasti virheellisyydetkin ovat tällöin helpommin tunnistettavissa kuin kokonaislukuoptimointiongelmaa minimoivaan tulosvektoriin piilotettuina arvoina.

Lisäksi, taisin näyttää tässä projektissa todeksi eräässä toisessa blogissa näkemäni hieman maagisen määritelmän reittioptimoinnille. Jos optimoimalla voi saada aurat lentämään portaiden yli niin maybe there really is some magic in the air?

Lähteet

[1] P. Mäkinen: Ambulanssien optimaaliseen sijoittamiseen ohjaava monitavoitemalli. Pro gradu -tutkielma, Turun yliopisto, 2018.

[2] IBM Knowledge Center: Using the LP format. https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.6.1/ilog.odms.cplex.help/CPLEX/GettingStarted/topics/tutorials/InteractiveOptimizer/usingLPformat.html

[3] M. P.L. Haslbeck: Algorithms for the Mixed Chinese Postman Problem. Final Report for an Interdisciplinary Project, Technische Universität Munchen, 2015.

[4] Informaatiota Travelling Salesman Problem historiasta, sovelluksista ja ajankohtaisista aiheeseen liittyvistä tutkimuksista:

http://www.math.uwaterloo.ca/tsp/index.html