Lukijamme sai taannoin innostuksen "Oulun kehätietä" käsitelleestä artikkelista ja intoutui miettimään vaihtoehtoisia reittejä Porin ja Kiteen välillä. Ja niitähän löytyi.
Tietotekniikan historian suurmiehiä oli alkuaikojen pioneeri, hollantilainen matemaatikko Edsger W. Dijkstra. Hänen nimensä on jäänyt elämään "Dijkstran algoritmissa", joka on tehokas menetelmä löytää paras reitti paikasta toiseen. Dijkstran työn varaan on tehty paljon uusien menetelmien kehitystä vuosikymmenien aikana, mutta useimmissa reitinlaskentajärjestelmissä se on jossain muodossa konepellin alla.
Mutta sen enempää Dijkstra kuin seuraajatkaan eivät ole löytäneet yhtä kriteeriä eikä tietenkään ratkaisua siihen kysymykseen, mikä on toiseksi paras reitti. Eikä siihen vastausta olekaan. Tietyön kiertämiseen tarkoitettu kiertotie on aivan eri asia kuin matkailijan hamuama reitti nähdä uusia maisemia.
Erilaisia menetelmiä on kehitetty paljon ja niistä on kirjoitettu väitöskirja jos toinenkin. Erään tukevahkon saksalaisen väitöskirjan innoittamana Teillä ja Turuilla on tehnyt kokeiluja suomalaisella Digiroad-aineistolla. Kokeiluväleinä, kuinkas muuten, Pori-Kitee ja sen lisäksi Helsinki-Rovaniemi.
Useat menetelmät toimivat siten, että kun yksi reitti laskettu, aineistosta poistetaan jollain kriteerillä tieosuuksia, ja jäljelle jääneistä taas haetaan paras reitti. Tätä toistetaan, kunnes haluttu määrä reittejä on plakkarissa.
Teillä ja Turuilla kokeili kuitenkin sakkomenetelmää: Jokaiselle käytetylle tieosuudelle annetaan jollain menetelmällä sakko. Kun sakkoa kertyy riittävästi, algoritmi löytää paremman vaihtoehdon jotain toista kautta. Jos lähelläkään ei ole kunnollista vaihtoehtoa, rapsakastikin sakotettu reitti kelpaa. (Poistomenettelyhän saattaa olla riskialtis, ellei olla huolellisia. Jos lähdetään Helsingin Erottajalta ja joka kierroksella yksi kaduista poistetaan aineistosta, neljännen kierroksen jälkeen matka päättyy siihen paikkaansa, koska kadut loppuvat.)
Käytetyssä menetelmässä annetaan sakkoa kertomalla tieosuuden "kustannus" luvulla f, joka saadaan varsin yksinkertaisesta kaavasta
f = A + B ((cos(x)+1)/2)
A, B ja C ovat mallin parametreja, joita säätämällä saadaan painotetuksi eri asioita. Muuttuja x kertoo, missä kohtaa reittiä ollaan: alussa x=-π, lopussa +π ja muualla jotain siltä väliltä. Mitä suurempi on parametrin C arvo, sen jyrkemmin painotetaan reitin keskiosaa.
Seuraavassa joitain tuloksia. Paremmuusjärjestys on musta, punainen, sininen, vihreä, ruskea, pinkki, harmaa, purppura. Kullakin valitulla parametrijoukolla on laskettu kahdeksan reittiä. Reittivalintojen painotus perustuu teiden nopeusrajoituksiin.
Pori-Kitee
A=1,5, B=0: Jokaisen kuljetun tieosuuden kustannus kerrotaan luvulla 1,5.
A=1,5, B=1,5, C=1: Reitin päissä sallitaan saman tien käyttö helpommin, mutta keskellä siitä sakotetaan. Pienempiä teitä valikoituu ajettavaksi.
A=3, B=-1,5, C=1: Päinvastoin kuin edellä: Reitin päissä sakotetaan ankarasti, mutta keskellä ollaan armeliaampia. Hajonta suurta, Helsingin nurkillakin käydään.
A=1,2, B=3,8, C=10: Kerroin on varsin lievä muuten, mutta keskivaiheilla varsin lyhyellä matkalla se nousee jyrkästi lukuun 5 asti. Jonkin verran tiiviimpi kuin edellinen.
Helsinki-Rovaniemi
Helsingin ja Rovaniemen välillä ei ole Päijänteen kaltaista estettä poikittain reitillä. Tässäkin reitit poikkeavat toisistaan varsin paljon.
A=1,5, B=0: Jokaisen kuljetun tieosuuden kustannus kerrotaan luvulla 1,5. Nopein reitti on nelostie, mutta 200 kilometrin kokonaispituuden eron sisään mahtuu monta mielenkiintoista reittiä.
A=1,2, B=3,8, C=10: Kerroin on varsin lievä muuten, mutta keskivaiheilla varsin lyhyellä matkalla se nousee jyrkästi lukuun 5 asti. Pinkki ja Purppura ovat lähteneet reiteille, jotka eivät ole aivan tyypillisiä Helsingin ja Rovaniemen välillä.
Reitit leikkaavat toisiaan monessa paikassa. Näistä palasista saa jo melkoisen monta yhdistelmää.
5 kommenttia:
Mielenkiintoinen laskukaava! Tein joitakin kokeiluja ja olet kuvaillut parametrien vaikutusta hyvin osuvalla tavalla. Uskoisin Google Mapsin ja vastaavien ohjelmien käyttävän jotain samantapaista laskukaavaa. Piti vielä piruuttaan kokeilla, mitä tapahtuu muutamilla epäkonventionaalisilla kertoimilla. B:n arvon muuntelu oli odotetusti tylsää ja negatiiviset A:n tai C:n arvot sekoittanevat systeemin mielettömäksi. Sen sijaan voisi saada aika mielenkiintoisia reittejä valitsemalla B:n negatiiviseksi, mutta itseisarvoltaan A:ta pienemmäksi (jos jälkimmäistä ehtoa ei käytä, niin systeemi ei luultavasti toimi).
Itse asiassa Pori-Kitee-skenaarioista kolmas on laskettu negatiivisella B:n arvolla: A=+3,0 ja B=-1,5. Se siis kääntää kosinipohjaisen käyrän "ylösalaisin". Kerroin on päissä 3,0 ja keskellä 1,5.
Kokeilujen perusteella kertoimen pitää olla vähintään luokkaa 1,3-1,4, jotta sillä on isompaa vaikutusta reitin valintaan.
Tuo kosinifunktiopäjäys on itse asiassa haverkosini-funktio, joka on samankaltainen kuin useammin nähty sisarensa haversini. Hav cos(x) = hav sin(180°+x). Kuvaaja on samankaltainen kuin kosinin, mutta koska negatiiviset arvot puuttuvat, luvun voi korottaa mielivaltaiseen potenssiin. Haversiniä käytettiin aikoinaan sekstanttilaskujen taulukoissa, koska sen ei-negatiivisuus tuottaa myös mahdollisuuden logaritmin ottamiseen.
Käytetyn kaavan rajoitteita on se, että se on symmetrinen puolenvälin suhteen. Jossain vaiheessa ajattelin katsella joitain muitakin vaihtoehtoja. Toinen tutkimisen arvoinen kehittämistoimi olisi laventaa sakotuspohjaa nykyisestä yksiulotteisesta kaksiulotteiseen. Nythän vain kuljetun polun legeihin sovelletaan sakkokerrointa. Yhtä laillahan sitä voitaisiin soveltaa vaikkapa vaikkapa 20 kilometrin leveydeltä. Jopa niin, että kauempana kerroin olisi alle 1, eli reittioptimaattoria houkuteltaisiin lähelle edellistä reittiä, muutta ei aivan kiinni.
No niinhän siinä se miinusmerkki kummittelikin. Tämä ratkaisi asian - teen sen mitä olen jo pidempään harkinnut ja hankin lasit näyttöpäätetyöskentelyä varten. Ei ollut nimittäin ensimmäinen kerta kun jää jokin tuollainen huomaamatta näön takia.
Oulu näyttäisi olevan ohittamaton paikka läntisissä reiteissä. Laskukaava ei näytä huomioivan Oulun "toista" ohitustietä vaihtoehtona.
Kaava kyllä ottaisi huomioon. Laskelmat on tehty Digiroadin aineistosta luodulla osajoukolla poimimalla tieosuudet, jotka ovat maanteitä ja katuja ja joiden toiminnallinen luokka on enintään 4. Ajatus on poistaa tutkimusaineistoista pienimmät kadut. Oulun kaupunki on syystä tai toisesta koodannut uuden Raitotien toiminnalliseen luokkaan 5 liityntäkatu, joka tarkoittaa asuntokatua. Ratkaisu ei vastaa esitettyjen toiminnallisten luokkien kuvausta, jossa Raitotien pitäisi kaiketi olla luokassa 3.
Hullujen keskiaukkojen ja muiden sellaisten kautta tapahtuvan reitityksen estämiseksi poiminnassa on otettu mukaan vain linkkityypit numeroltaan enintään 6. Lossit ja lautat ovat tyyppiä 21 ja siksi käytetty ohjelma ei tuolla aineistolla ei löydä tietä mantereelta Hailuotoon.
Lähetä kommentti