JultikaUniversity of Oulu repository

Tiivistelmä

Nopeimman reitin haku tieaineistolla on osa monien ihmisten arkipäivää esimerkiksi käytettäessä mobiililaitteita. Optimaalisen reitin haku kahden pisteen välillä on aihe, josta on olemassa paljon aiempaa tutkimustietoa. Klassisia algoritmeja, jotka ratkaisevat nopeimman reitin ongelman graafissa ja joita voidaan hyödyntää myös tieaineistolla ovat Dijkstran algoritmi ja A* -algoritmi. Uusimmissa tutkimuksissa on kehitetty nopeita algoritmeja, joille tarvittava reittiaineisto esikäsitellään nopeuden parantamiseksi. Tämän työn keskeisenä tutkimuskysymyksenä on selvittää, miten klassisia reitinhakualgoritmeja voidaan optimoida Suomen kattavalla Digiroad-tieaineistolla aiemmasta tutkimuksesta löytyvin menetelmin. Työssä tutkitaan tietorakenteiden optimointia tieaineistolle, keskinopeuden käyttöä heuristiikkana matka-ajan optimoinnissa sekä miten tieaineiston metadataa voidaan hyödyntää algoritmien optimoinnissa. Saatuja tuloksia verrataan esikäsittelyä hyödyntäviin algoritmeihin.

Kirjallisuuskatsaus sisältää käsittelyn klassisista reititysalgoritmeista, tieaineiston erityispiirteistä sekä miten esikäsittelyä hyödyntävien menetelmien kehitys on vaikuttanut tutkimukseen. Lisäksi käsitellään tietorakenteiden roolia reititysalgoritmien toiminnassa sekä millaisia tuloksia eri optimointimenetelmien yhdistelmillä on saatu. Tämän työn tutkimusmenetelmänä on suunnittelutiede (Design Science). Menetelmän avulla luotu artefakti lukee Digiroad-aineistoa ja toimii yhtenäisenä alustana kolmelle erilaisille koejärjestelylle, jotka vastaavat esitettyihin tutkimuskysymyksiin. Jokaisessa koejärjestelyssä kerättiin tietoa algoritmien toiminnassa suorituskyky ja laatumittareilla käyttäen viittäsataa satunnaisesti valittua pisteparia.

Tietorakenteiden ja algoritmien koejärjestelyn keskeisenä tuloksena havaittiin A* -algoritmin suoriutuvan 3,59 kertaa nopeammin kuin Dijkstran algoritmi Digiroad-aineistolla. Lisäksi tietorakenteiden käytännön toteutuksella on suuri vaikutus algoritmien nopeuteen. Binäärikeon toimintaa optimoimalla voitiin parantaa reitityksen nopeutta A* -algoritmilla 6,43 kertaisesti verrattuna perinteiseen binäärikekoon. Keskinopeutta käsittelevässä koejärjestelyssä tutkittiin A* -algoritmin heuristiikkaa ja millä arvioidulla keskinopeudella saadaan parhaat tulokset heuristiikassa linnuntietä hyödyntäen. Paras tasapaino reititysnopeuden ja optimaalisesta reitistä poikkeaman välillä saavutettiin arvoilla 70–90 km/h. Tällöin poikkeama oli 0,03–1,61 % optimaalisesta ratkaisusta reititysajan ollessa 3,54–14,84 kertaa parempi kuin referenssinä toimineessa Dijkstran algoritmissa. Kolmannessa koejärjestelyssä hyödynnettiin Digiroad-aineiston metatietoja luomalla niiden pohjalta erilaisia kaksitasoisia hierarkkisia algoritmeja käyttäen pohjana A* -algoritmia ja aiempien koejärjestelyjen tuloksia tavoitteena parantaa reititysaikoja. Tulokset voidaan jakaa kahteen ryhmään. Laadukkaimmilla algoritmeilla saavutettiin 14,25–18,27 kertainen parannus Dijkstran algoritmiin verrattuna poikkeaman optimaalisesta reitistä ollen 0,79–0,92 %. Nopeimmilla algoritmeilla saavutettiin 26,36–37,54 kertainen parannus Dijkstran algoritmiin, mutta poikkeama optimaalisesta reitistä oli tällöin 2,60–3,21 %. Tutkituilla algoritmeilla voidaan lähestyä nopeudeltaan yksinkertaisia esikäsittelyä hyödyntäviä algoritmeja, jos poikkeama optimaalisesta reitistä on hyväksyttävissä.