Minimikustannuspolkujen kautta maaliin – osa 1
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!
