Reitinhaun optimoinnin haasteet

Abstract

Tänä päivänä reitinhaku on osa jokapäiväistä elämäämme ja yleistyy jatkuvasti. Reitinhaun keskeisimpänä tavoitteena on löytää lyhyin reitti annetun kahden pisteen välillä tarkasteltavasta ympäristöstä. Reitinhakua hyödynnetään muun muassa autonomisten robottien ohjauksessa, tietokoneohjaamien videopelihahmojen liikkumisessa ja karttasovellusten navigoinnissa. Useissa sovelluskohteissa reitinhaulta vaaditaan tehokkuutta, jotta saavutettaisiin toivottuja lopputuloksia. Reitinhaku on historiallisesti ollut tasapainottelua reitin laskemiseen käytetyn ajan ja lasketun reitin pituuden välillä. Monet tehokkuuteen vaikuttavat tekijät ovat toisistaan riippuvaisia, mikä puolestaan tekee reitinhaun optimoinnista hankalaa. Tässä työssä tarkastellaan yhden toimijan vapaan liikkeen reitinhaun optimointia tieteellisen kirjallisuuden avulla ja reitinhaun tehokkuutta tarkastellaan lasketun reitin pituuden ja laskemiseen käytetyn ajan näkökulmasta. Työssä käsitellään reitinhaun kaksi pääkomponenttia, jotka ovat graafi ja algoritmi. Näistä osakokonaisuuksista käsitellään graafien erilaisia toteutustapoja sekä reitinhaussa käytettävien algoritmien eroja. Työn tavoitteena on tuoda esiin reitinhaun kompleksisuus ja vertailla erilaisten reitinhakutoteutusten vahvuuksia ja heikkouksia. Tutkimuksessa havaittiin reitinhakutoteutuksien välillä olevan suuria eroja. Erot toteutusten välillä aiheutuvat reitinhakutavoitteen, graafitoteutuksen ja reitinhakuun käytettävän algoritmin yhteisvaikutuksesta. Reitinhakutoteutukseen vaikuttavat myös reitinhaun ulkopuoliset tekijät, kuten reitinhakua suorittavan laitteiston ominaisuudet, toteutuksen muodostamiseen käytettävissä oleva aika. Tästä syystä optimaalisen reitinhaun saavuttamiseksi tulee reitinhakua käsitellä kokonaisuutena ja huomioida reitinhaun tehokkuuteen vaikuttavien osien vaikutus toisiinsa. Tutkimuksessa todetaan reitinhaun optimaalisuuden määräytyvän sovelluskohteen perusteella ongelman moniulotteisuuden vuoksi, koska tarkasteltavan tapauksen piirteet määräävät optimaalisen reitinhaun luonteen.