Reittihaku

Tämä on vastaus kotitenttiin kurssille Verkkoteoria [1] keväällä 2004.

Johdanto

Matkustuksen suunnitteluun on nykyisin käytettävissä WWW:ssä useita reittioppaita, jotka yhdistelevät aikataulutietoja. Merkittäviä ovat muun muassa seuraavat:

VR:n palvelu hakee annetun lähtöaseman, määräaseman sekä vaihtoehtoisesti aikaisimman lähtöhetken tai myöhäisimmän saapumishetken perusteella sopivia junayhteyksiä. Saksan vastaava palvelu kattaa koko Euroopan ja raideliikenteen lisäksi myös muita kulkumuotoja sekä paikkatietoja. YTV:n palvelu on tarkoitettu pääkaupunkiseudun joukkoliikenteen käyttäjille, ja se sisältää kaikki joukkoliikenteen aikataulut sekä viralliset kävelyreitit kotiosoitteisiin.

Seuraavassa tarkastellaan kuvaillunkaltaisten palveluiden algoritmista hakuongelmaa, jonka yksinkertainen versio on perinteinen lyhimmän polun ongelma.

Reittihaun määrittely

Reittihaussa tarkoituksena on löytää annetusta lähtöpaikasta annettuun kohdepaikkaan ajasta riippuvia yhteyksiä hyödyntäen. Lähtö- ja kohdepaikkojen välillä voidaan käydä vaihtopaikoissa, joissa siirrytään yhteydestä toiseen. Mikä tahansa ratkaisu ei kelpaa, vaan haetaan nopeinta reittiä aikaisimman lähtöhetken jälkeen tai ennen viimeisintä saapumishetkeä. Nopeimmalla reitillä tarkoitetaan, ettei vaihtamalla käytettyjä yhteyksiä ole mahdollista lähteä myöhemmin tai päästä aikaisemmin perille ellei saapumishetki tai lähtöhetki siirry vastaavasti.

Lisäominaisuuksina voidaan rajoittaa yhteystyyppejä, rajoittaa vaihtojen määrää tai selata aikaisempia tai myöhäisempiä nopeimpia yhteyksiä.

Yhteydet saadaan aikatauluista, joissa kerrotaan kunkin kulkuneuvon osalta pysähtymispaikat sekä -hetket. Paikat voidaan kuvata verkon solmuina ja yhteydet väleinä, joiden paino kuvaa kuluvaa aikaa. Välin paino tietyllä solmuunsaapumishetkellä saadaan katsomalla aikataulusta, kuinka pitkän ajan kuluttua lähtevistä kulkuneuvoista ensimmäinen on perillä. Ellei mikään kulkuneuvoista käy kohdesolmussa, väliä ei ole.

Algoritmille annetaan näin ollen syötteenä aikatauluista saatavat verkon solmut ja välien painoihin tarvittavat tiedot. Edelleen annetaan lähtö- ja kohdesolmut sekä lähtöhetki. Jos vaatimuksena on lähtöhetken sijaan saapumishetki, voidaan algoritmia varten kääntää lähtö- ja kohdesolmut sekä yhteystiedot toisinpäin. Algoritmilta odotetaan tuloksena polkua, joka kuvaa lyhimmän yhteyden.

Yksinkertainen hakualgoritmi

Kenties yksinkertaisin algoritmi edellisen luvun vaatimusten täyttämiseen on leveys ensin -haku (breadth-first search, BFS) painotetussa verkossa prioriteettijonolla (best-first search, BFS; priority-first search, PFS). Alkuhetkellä ollaan lähtösolmussa, ja algoritmin edetessä tutkitut polut laajenevat aikajärjestyksessä lähtösolmusta joka suuntaan. Kun ollaan päästy solmuun, siitä lähtevät välit lisätään prioriteettijonoon. Lopulta päästään kohdesolmuun, ja algoritmin suoritus on valmis. Vaihtoehtoisesti jatkoyhteydet loppuvat ja prioriteettijono tyhjenee, jolloin algoritmin suoritus päättyy tulokseen, että lähtötiedoissa haettua reittiä ei ole.

Algoritmin oikeellisuus perustuu siihen, että prioriteettijono ylläpitää eräänlaista tapahtumahorisonttia, ja algoritmin suoritusjärjestys vastaa mahdollisia yhteysjärjestyksiä: ensimmäinen reitti, jota solmuun päästään, on myös nopein. Tähän perustuu myös algoritmin tehokkuus aikavaatimuksen ollessa lineaarinen solmujen ja välien summan suhteen. Jokainen verkon solmu täytyy tarkastella korkeintaan kerran eli ensimmäisellä saapumiskerralla. Edelleen jokainen väli tarkastellaan vain lähtösolmun tarkastelun myötä.

Kirjan esitys asiasta

Kurssin oppikirjassa, Vesa Savolaisen Verkkoteoriassa [5], luku kuusi käsittelee minimietäisyyksiä ja reittejä. Tässä käsiteltävän aiheen kannalta oleellinen luku on "6.4. Etäisyys ajan funktiona", jossa tarkastellaan lyhimmän polun hakua tilanteissa, joissa välien painot riippuvat ajasta:

Jos lyhimmälle polulle ilmaantuu este, kuten onnettomuus, liikennesuma tms., jonka vaikutus reitin edullisuuteen riippuu ajasta jonkin funktion mukaan lähtöhetkellä solmusta vi, saadaan käyttöön luvun 6.3 apparatuuri hieman mutkikkaammalla tavalla. Merkitään:
dij(t) ilmoittaa välin (vi,vj) painon solmusta vi laskettuna ajanhetkellä t
— —

Vaikka tätä ei olekaan mainittu, kirjassa esitetty dynaamisen ohjelmoinnin algoritmi 6.4.1. sopii myös reittihakuun, kunhan aikataulut on käsitelty tässä edellä määritellysti.

Tehostavat heuristiikat

Sovellusaluetta tarkastelemalla verkkohakualgoritmeja voidaan virittää nopeammiksi ja vähemmän tilaa käyttäviksi. Hyödyllinen lisätieto on kustannusarvio kustakin solmusta kohteeseen, joka saadaan esilaskemalla tai vaikkapa euklidisesta etäisyydestä jaettuna kulkuvälineiden huippunopeudella. Sitä voidaan käyttää heuristiikkana rajoittamaan tutkittavia yhteyksiä A*-hakualgoritmin [6] mukaisesti: polun kestoon lisättävä kustannusarvio rajoittaa kohteesta poispäin kulkevien polkujen tutkintaa. Algoritmin tulokseen heuristiikka ei vaikuta arvion ollessa minimiä suurempi.

Kokeiltavia yhteyksiä voidaan rajoittaa myös huomioimalla, että samaan kulkuvälineeseen ei hyödytä tulla toista kertaa reitin aikana, sillä samaan tilanteeseen päästään pysymällä kulkuvälineessä ensimmäisellä kerralla.

Yhteenveto

Edellä tarkasteltiin aikataulutiedoista reittejä yhdistelevien palveluiden toteutuksessa esiintyvää verkkohakuongelmaa. Ongelman määrittelyn jälkeen kuvattiin verkkoesitys ja tarkasteltiin suoraviivaisia algoritmeja sekä niiden tehostamista heuristiikoilla.

Algoritmien testauksessa tarvittavaa aikatauluaineistoa on saatavilla WWW:ssä, algoritmit voisi toteuttaa testausta ja vertailua varten.

Viitteet

[1]
Verkkoteoria, http://www.cs.jyu.fi/~jorma/verkko.html
[2]
VR Matkahaku, http://service.vr.fi/ticket/application
[3]
YTV:n reittiopas, http://www.ytv.fi/reittiopas
[4]
Die Bahn TravelService, http://reiseauskunft.bahn.de/bin/query.exe/en
[5]
Vesa Savolainen, Verkkoteoria, WS Bookwell, Porvoo 2001
[6]
Wikipedia, A-star search algorithm, http://en.wikipedia.org/wiki/A-star_search_algorithm, versio "11:22, 15 Apr 2004"

2004-04-22
http://www.iki.fi/Tuukka.Hastrup/2004/reittihaku
© 2004 Tuukka Hastrup (Tuukka.Hastrup@iki.fi)