Tik-76.022 Tietorakenteet ja algoritmit suunnittelutehtävä

3.5.2001

Jonas Alam              52317M

Pasi Kuusela           

Esko Eerola            

1. Yleiskuvaus

Infopolis-kaupungin matkailutoimisto haluaa toteuttaa järjestelmän, jonka avulla on mahdollista tarjota kaupungin asukkaille ja matkailijoille kätevästi tietoa kaupungin erilaisista palveluista. Järjestelmän työnimenä on MOKI. Lähtökohtana on se, että tietoihin päästään käsiksi langattomasti sopivan kannettavan laitteen avulla, jonka sijainti pystytään päättelemään riittävällä (muutaman metrin) tarkkuudella.

Ratkaisua varten voidaan olettaa valmiina seuraavia asioita:

      Henkilön sijainti voidaan paikantaa riittävällä tarkkuudella, jotta järjestelmä voi verrata tätä tietoa karttatietoon ja tehdä luotettavia päätelmiä henkilön sijainnista kaupungissa.

      MOKIn peruskarttatietoina on Infopoliksen digitaalisesti esitetty kartta, joka sisältää seuraavaa tietoa:

      kaikki kadut, tiet ja julkiset kulkuväylät

      puistot, vesialueet

      rakennukset

      julkiset nähtävyydet

      palvelupisteet (esim. kaupat, ravintolat, ...)

      julkisen liikenteen reitit ja pysäkit

      Karttapohjasta ei ole erikseen toteutusta eri mittakaavoihin. Katujen ja kohteiden kokoa koskevaa tietoa voidaan käyttää hyväksi, kun karttaa skaalataan suurempaan mittakaavaan, jolloin osa yksityiskohdista täytyy jättää pois.

Alustavassa suunnittelussa järjestelmä on jaettu kolmeen moduuliin, reittitiedon hallintaan (RTH), karttatiedon hallintaan (KTH) sekä käyttöliittymään (KL). Näistä ensiksi mainittu hoitaa kaiken logiikan, joka liittyy kulkureittien suunnitteluun. Karttatiedon hallintaa tarvitaan siihen, että voidaan näyttää käyttäjälle, missä kulloinkin liikutaan, missä kiinnostavat kohteet ovat sekä mikä on suunniteltu reitti. Käyttöliittymän avulla hoidetaan varsinaiset komennot, joilla järjestelmää ohjataan ja se, mitä tulostuu päätelaitteen kuvaruudulle.

Suunnittelutehtävä on toteutettu silmälläpitäen Java-implementointia.

2. Moduulin toiminnallisuus

RTH-moduuli antaa tiedon optimaalisesta reitistä kahden pisteen välillä. Käyttäjän käyttöliittymälle antamien toiveiden mukaan voidaan matka kulkea kolmella eri tavalla:

1. mahdollisimman paljon julkisilla kulkuneuvoilla
2. kokonaan kävellen
3. edellä mainittujen yhdistelmänä, joka on tehtävänantoon nähden ylimääräinen ominaisuus

Moduuli saa karttatiedonhallinnalta tiedon siitä minkä kahden solmun välillä reittiä optimoidaan ja antaa tuloksena KTH moduulille kuljettavan reitin, solmujen väliset kulkutavat, mahdolliset julkisen liikenteen vaihdot ja matkan kokonaisajan.

3. Tiedon siirto eri modulien välillä

Käyttöliittymä lähettää RTH:lle kulkutavan int muuttujana, jossa esimerkiksi nolla tarkoittaa kävelemistä, yksi pelkkiä julkisia kulkuvälineitä ja kaksi edellä mainittujen yhdistelmää. KTH lähettää lähtö -ja maalipisteen String tai int-oliona.

Ehdotus optimaaliseksi reitiksi lähetetään KTH:lle seuraajalistana, jonka alkiot ovat abstrakteja tietotyyppejä sisältäen solmun String-muotoisen nimen ja kulkutavan. Kulkutapa esitetään String-muuttujana.

 

Kuva 1. Tiedon siirto eri moduulien välillä.

 

4. Ohjelman tarvitsemat tietorakenteet

      Verkko esitetään yhtenä kokonaisuutena seuraajalistana siten, että kävely- bussi- ja metrolinjat esitetään samassa verkossa. Lisäksi verkko oletetaan yhtenäiseksi ja suunnatuksi. Raitiovaunut rinnastetaan busseihin ja junat metroihin, koska kulkunopeudet näillä välineillä likimain vastaavat toisiaan. Tämä tarkoittaa yksinkertaisesti käytännössä sitä, että näille annetaan sama paino, joka luetaan samasta kentästä. Bussi- ja raitiovaunulinjojen koodeina käytetään kyseisten linjojen oikeita tunnuksia ja ne tallennetaan String-olioiksi (esimerkiksi "bussi:102T" tai "raitiovaunu:3T").

      Seuraajalistan ensimmäinen alkio on olio, joka sisältää tiedon solmun nimestä, int-tunnuksesta ja koordinaateista.

      Jokainen seuraajalistan särmä esitetään oliona, joka kuvaa kaaren ominaisuuksia. Oliossa on seuraavat kentät:

      viittaus kohdesolmuun

      int kävelyn painolle

      int bussi/raitiovaunu yhteyden painolle

      int metro/juna yhteyden painolle

      String-vektori bussi/raitiovaunulinjoille

Oliot on nimetty todellisilla nimillään. Esimerkiksi "Otakaari 15, pysäkki" tai "Otakaari-Jämeräntaival, risteys". Solmujen tunnisteina käytetään juoksevaa numerointia.

 

Kuva 2. Seuraajalista: vasemmalla piste-olioita ja kaari-olioita oikealla.

 

Kaarien painot graafissa kuvaavat kahden solmun välisen matkan kulkemiseen kuluvaa aikaa. Reittivaihtoehtojen painojen asettamisessa sovelletaan kaavaa t=s/v siten, että kävely-yhteyden paino on solmujen välinen etäisyys metreinä jaettuna arvioidulla kaikille vakiolla kävelynopeudella. Kävelynopeus on siis kaikissa hauissa sama, eikä käyttäjä pysty asettamaan arvoksi omaa kävelynopeuttaan. Tämä siksi että kävelyn paino on verrattavissa julkisten kulkuvälineiden vastaaviin painoihin, jotka ilmoitetaan aikana. Julkisten yhteyksien painot arvioidaan asettamalla paikallisten liikenneyhtiöiden aikataulujen ajat tai jakamalla matka arvioidulla kulkuvälineen nopeudella. Jos yhteyttä kyseiselle kulkutavalle ei ole, painoksi asetetaan hyvin suuri luku.

      Haulla saavutettu reitti tallennetaan linkitetyksi listaksi, jonka alkiot ovat olioita ja sisältävät seuraavat kentät:

      int-kenttä tunniste

      point-kenttä sijainti

      String-kenttä kulkutapa + linja

Tähän viitataan jatkossa nimellä reittiolio.

      Solmujen tunnistamiseen käytetään object-taulukkoa, jossa ensimmäisellä rivillä ovat solmujen int-tunnisteet ja toisella String-nimet.

      PFS-haussa käytetään apuna 3xV int taulukkoa, jonka sarakkeina ovat parent, visited ja priority.

 

      Vaihtojen määrän optimoinnissa käytetään apuna String-vektoria.

 

5. Eri toimintojen toteutus

Lyhimmän reitin etsiminen

Etsittäessä lyhintä reittiä voidaan törmätä kolmeen erilaiseen tilanteeseen, joista kukin vaatii erilaisen käsittelyn.

1. Jos reitti kuljetaan pelkästään kävellen, haetaan lyhin reitti käyttäen PFS-algoritmia (Priority First Search) huomioiden kutakin särmää kuvaavasta oliosta ainoastaan kävelyn paino, ei siis bussin tai metron painoa.

Prioriteettina käytetään:

kaarien painojen summa lähtösolmusta käsiteltävään solmuun

+

geometrinen etäisyys käsiteltävästä solmusta kohdesolmuun

Geometrinen etäisyys lasketaan pisteiden koordinaateista.

PFS-algoritmin toiminta:

1. otetaan käsiteltäväksi lähtösolmu ja lisätään se puun ensimmäiseksi alkioksi
2. lisätään reunukseen solmut, joihin on yhteys lähtösolmusta ja lasketaan niille prioriteetti ja lisätään prioriteetti priority-taulukkoon.
3. lisätään puuhun se reunuksen solmu jolla on pienin prioriteetti
4. lisätään reunukseen solmut joihin on yhteys lisätystä solmusta elleivät ne jo kuulu puuhun tai reunukseen
5. jos solmu kuuluu jo reunukseen päivitetään prioriteetti mikäli vanha prioriteetti on suurempi kuin uusi prioriteetti
6. toistetaan kohtia 3-6 niin kauan kunnes kohdesolmu on lisätty puuhun ja merkitään reitin kulkutavaksi "kävely".

Lisäksi ylläpidetään taulukoita visited ja parent sekä kekoa prioriteettijonolle.

2. Kuljettaessa mahdollisimman paljon julkisilla kulkuvälineillä, etsitään ensin käyttäjän lähtöpistettä lähinnä oleva pysäkki PFS-haulla. Prioriteeteissa ei oteta huomioon geometristä tekijää, vaan ainoastaan todellinen kävelyn paino. Haku toimii seuraavasti:

      edetään normaalin PFS-haun mukaisesti

      aina kun solmu liitetään puuhun tutkitaan onko se bussipysäkki/tavoitepiste

      jatketaan hakua niin kauan kunnes bussipysäkki/tavoitepiste löytyy. Tallennetaan bussipysäkit niitä varten varattuihin int-kenttiin.

Sama toistetaan tavoitepisteelle ja etsitään sitä lähin pysäkki, jonka jälkeen haetaan reitti löydettyjen pysäkkien välillä PFS-haulla siten että vain bussi- ja metroyhteyksien painot sekä pisteiden välinen geometrinen etäisyys huomioidaan prioriteetteihin. Erona normaaliin PFS-hakuun on se, että jokaisen reunukseen liitettävän solmun kohdalla tutkitaan sekä bussi- että metroyhteyden painot ja valitaan näistä pienempi. Jos päätepysäkki ja lähtöpysäkki ovat samat, ei luonnollisesti suoriteta julkisen kulkuvälineen reitin optimointia. Verkko oletetaan yhtenäiseksi myös julkisten kulkuvälineiden osalta. Tällöin on välttämättä olemassa reitti kahden pysäkin välillä.

3. Haettaessa parasta reittiä kävelyn ja julkisten kulkuvälineiden yhdistelmänä eli etsittäessä absoluuttisesti nopeinta reittiä käytetään jälleen PFS-hakua, mutta prioriteeteissa otetaan huomioon sekä kävelyn että metron ja bussin painot. Muutoin haku noudattaa optimaalisen kävelyreitin etsimisessä käytettyä hakua. Liitettäessä solmu reunukseen tutkitaan siis mitä yhteyksiä solmujen välillä on olemassa ja minkä prioriteetti näistä on pienin.

Saadusta PFS-puusta reitti alku- ja päätepisteen välillä saadaan seuraavasti:

      tutkitaan parent-taulukosta päätesolmun isä ja tallennetaan päätesolmu seuraajalistan viimeiseksi alkioksi

      siirrytään isäsolmuun, tutkitaan sen isä ja tallennetaan solmu listan toiseksi viimeiseksi alkioksi ja lisätään linkki viimeiseen alkioon

      jatketaan vastaavasti, kunnes löydetään lähtöpiste

Vaihtojen määrän optimointi

Kun on löydetty julkisilla kulkuvälineillä kuljettava reitti suoritetaan vaihtojen optimointi. Tämä tapahtuu seuraavasti:

1. aloitetaan lähtöpisteestä ja katsotaan millä linjoilla päästään seuraavaan pisteeseen ja tallennetaan linjat vektoriin
2. edetään listassa seuraavaan alkioon ja katsotaan millä linjoilla päästään taas seuraavaan alkioon. Linjoja vertaillaan siten, että käydään vektorin linjat lävitse yksi kerrallaan ja katsotaan löytyykö linja kyseisestä alkiosta. Jos linjaa ei löydy, poistetaan se vektorista.
3. Näin jatketaan, kunnes ollaan poistamassa viimeistä alkiota, jolloin ollaan pisteessä jossa suoritetaan vaihto tai kunnes ollaan päätepisteessä.
4. Tallennetaan reittiolion kulkutapa-alkioksi vaihto- / päätepisteeseen asti kyseinen linja
5. Algoritmia toistetaan, kunnes saavutaan päätepisteeseen

6.Ratkaisun perustelut ja analyysi

Verkon rakenne ja hakualgoritmin valinta

Verkon toteuttamisessa harkittiin alunperin sekä seuraajalistaa että matriisia. Näistä valittiin seuraajalista. Vaikka matriisissa olisi voinut soveltaa PFS:ään verrattuna tehokkaampaa Dijkstran algoritmia (Dijkstra O(E) harvoille verkoille, PFS O((E+V)logV) ) matriisin vaatiman tilan kulutus olisi ollut liian suuri verrattuna saavutettuun tehokkuuteen. PFS-haun geometrisen variaation yksi merkittävimmistä eduista on se, että se ei lähde hakemaan joka suuntaan, vaan geometrisen etäisyyden ansiosta osaa suuntautua oikeaan suuntaan ja näin ollen haku on huomattavasti nopeampi ja tehokkaampi.

Tarkastellaan esimerkkinä 100 000 solmun suunnattua verkkoa, josta jokaisesta solmusta on yhteys neljään muuhun solmuun. Verkko on harva ja Dijkstralle O-notaatio tuottaa arvon 4* 100 000. PFS:lle O-notaatio on puolestaan (4*100 000 + 100 000)*log 100 000, joka on luokkaa 10^7 käytettäessä kaksikantaista logaritmia, joten Dijkstran voisi arvioida noin 10-20 kertaa tehokkaammaksi algoritmiksi.

Toisaalta tilankulutuksessa Dijkstran tarvitsema VxV yhteysmatriisi vaatisi muistia vähintään 10^5*10^5=10^10 bittiä, käytännössä enemmän kun matriisiin olisi vielä tallennettu tiedot mm. käytettävissä olevista bussilinjoista, koordinaateista yms. Tämä tarkoittaisi käytännössä levymuistiin turvautumista. PFS:n tarvitsema seuraajalista kuluttaa muistia suunnilleen määrän (V + E) * solmuun tallennetun tiedon määrä = (100 000 + 400 000) * 100 tavua = 50 Mt eli vajaa tuhannesosa matriisin vaatimasta määrästä. 50 Mt voidaan hyvin säilöä keskusmuistiin, jonka käyttö kompensoi hyvin Dijkstran tarjoaman nopeuseron. Seuraajalistan laajennettavuus on myös omaa luokkaansa, koska tehoero säilyy suunnilleen samana riippumatta alkioiden määrästä. Sen sijaan solmujen määrän satakertaistaminen vaatisi muistia seuraajalistalla viitisen tuhatta megatavua ja matriisilla suunnilleen 100 teratavua.

Seuraajalistan alkio muodostuu oliosta, jolla on seitsemän kenttää. String-nimeä käytetään, koska KTH suosinee solmujen selkokielistä nimeämistä. Int tunnistetta tarvitaan alkioiden tunnistamiseen eri algoritmeissa, koska tällöin voidaan käyttää taulukon indeksiä solmun tunnisteena. Point-kenttää käytetään geometrisen etäisyyden määrittämiseen PFS-haussa. Vaikka alkioissa on paljon tietoa, se ei kuitenkaan ole olennaista muistin kulutuksen kannalta, sillä seuraajalistalla muisti ei muodostu pullonkaulaksi.

Verkon päivitettävyys on listarakenteesta johtuen erittäin hyvä. Uusien solmujen lisääminen ja vanhojen poistaminen ovat yksinkertaisia joskin aikaa vieviä operaatiota. Samoin seuraajalistan kenttien muokkaus on helppoa oliorakenteen ansiosta. Päivityksestä ei ole kuitenkaan tehty reaaliaikaista, koska se hankaloittaisi järjestelmän toimintaa huomattavasti.

Verkko on oletettu yhtenäiseksi lähinnä siksi, että pelkästään julkisilla kulkuvälineillä -vaihtoehto olisi mahdollista toteuttaa inhimillisin resurssein.

Päädyimme käyttämään PFS-haussa geometrisen etäisyyden laskentaa lukuun ottamatta lähimmän bussipysäkin etsimistä. Haittapuolena tässä on lausekkeen d = sqrt( (x-x₀)²+(y-y₀)² ) laskemiseen kuluva aika, sillä tämä operaatio sijoittuu silmukan sisään ja voi toistua hyvin monia kertoja yhden haun aikana. Toisaalta geometrisen etäisyyden laskeminen auttaa suuntaamaan haun oikein.

Suurilla verkoilla, kuten tässä tapauksessa, tämän tuoma hyöty korostuu. Oletetaan hyvin laaja verkko, jonka solmut ovat tasaisesti jakautuneet. Jos PFS-haussa lasketaan geometrinen etäisyys, läpikäytävien solmujen määrä on suunnilleen verrannollinen r:ään, joka on lähtö ja kohdepisteen välinen etäisyys. Tosin joka kerta joudutaan laskemaan neliöjuuren arvo, mikä vie vakioajan. Tällöin geometrisen etäisyyden huomioon ottaminen johtaisi haun ajankulutuksen olevan verrannollinen a*r:ään, jossa a on neliöjuurilausekkeen laskemiseen kuluvaa aikaa kuvaava vakio. Toisaalta jos geometrista etäisyyttä ei lasketa, on läpikäytävien solmujen määrä verrannollinen r:n neliöön. Vaikka termi a voi olla suuri, on tämä vaihtoehto suurilla verkoilla tehokkaampi.

Vaihtojen optimointi

Kun paras bussi/metroreitti on löydetty, voidaan reitti kulkea monella eri tavalla kun otetaan huomioon eri linjojen mahdollisuudet. Päätimme, että emme ota huomioon eri metrolinjoja, koska tämä ei toisi mainittavaa lisäarvoa moduulille eikä palvelulle.

Bussireittien kohdalla päätimme, että emme etsi pienintä vaihtojen määrää, vaan tyydymme siihen, että löydämme kohtuullisen pienen vaihtojen määrän. Suurimmassa osassa tapauksia saadaan kuitenkin paras vaihtoehto. Tällä ominaisuudella pystyimme nopeuttamaan palvelua hieman, kun kaikkia bussilinjoja ja linjayhdistelmiä ei tarvitse käydä läpi.

 

Moduulin ongelmat ja puutteet

Äskeiseen kappaleeseen viitaten parhaan reitin valinnan puutteeksi voisi todeta sen, että hakualgoritmi ei ota millään tavalla huomioon bussin tai metron vaihtamiseen kuluvaa aikaa, eikä myöskään tarjoa välttämättä kaikissa tapauksissa parasta vaihtojen yhdistelmää.

Järjestelmämme ei myöskään huomioi vuorokaudenaikaa. Vuorokaudenaika voisi vaikuttaa liikkumisnopeuteen kaupungilla esimerkiksi ruuhka-aikana, tai bussit ja metrot eivät yleensä kulje yhtä usein öisin kuin päivisin.

 

Parannusehdotuksia

Moduuli voisi myös ottaa huomioon bussiaikataulut, niin että käyttäjä voisi mennä sillä bussilla/metrolla joka lähtee seuraavaksi.

Pohdimme myös sellaista mahdollisuutta, että moduulimme pitäisi kirjaa suosituimmista hauista ja tarkastaisi aina ensimmäiseksi löytyykö haettava reitti suosituimpien hakujen listalta. Jos haettava reitti löytyy suosituimpien listalta, säästetään huomattavasti aikaa, kun PFS-hakua ei tarvitse tehdä. Suosituimmat reitit olisi tallennettuna binääripuuhun, minkä takia niiden hakeminen ei veisi paljon aikaa. Ohjelma pitäisi kirjaa suosituimmista hauista ja päivittäisi binääripuuta sellaisina vuorokaudenaikoina, milloin ohjelma ei ole ruuhkautunut, esimerkiksi aamuyöllä.