haku: @keyword Reititys / yhteensä: 67
viite: 2 / 67
| Tekijä: | Päivinen, Jussi |
| Työn nimi: | Development of route finding algorithm for dynamic ride sharing application |
| Dynaamisen kyydinjakosovelluksen reitinhakualgoritmin kehittäminen | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2016 |
| Sivut: | 54 Kieli: eng |
| Koulu/Laitos/Osasto: | Perustieteiden korkeakoulu |
| Oppiaine: | Ohjelmistotekniikka (T-106) |
| Valvoja: | Malmi, Lauri |
| Ohjaaja: | Nordström, Miika |
| Elektroninen julkaisu: | http://urn.fi/URN:NBN:fi:aalto-201611025475 |
| Sijainti: | P1 Ark Aalto 4803 | Arkisto |
| Avainsanat: | sharing economy taxi routing algorithms jakamistalous taksi reititys |
| Tiivistelmä (fin): | Vedia Taxi on mobiilisovellus, joka mahdollistaa taksikyytien jakamisen samaan suuntaan matkustavien ihmisten kesken. Jakamisen mahdollistaa algoritmi, joka yhdistelee eri ihmisten reittejä. Algoritmi pystyy kuitenkin yhdistämään vain reittejä, joissa kaikki ihmiset lähtevät samasta lähtöpisteestä. Ihmiset eivät myöskään voi liittyä kyytiin matkan varrelta. Työn tarkoituksena on jatkokehittää algoritmia niin, että kyytiin olisi mahdollista liittyä mistä tahansa. Uutta algoritmia varten vertailtiin neljää reitityspalvelua keskenään. Nämä reitityspalvelut tuottavat reittiohjeet ja aika-arviot reiteille. Google Maps valittiin parhaaksi reitityspalveluksi, koska sen aika-arviot reiteille olivat tarkimmat. Reittiohjeissa oli joitakin eroja eri reitityspalveluiden välillä, mutta kaikki niistä olivat tarpeeksi hyviä. Google Maps ei muodostanut reittejä kaikista nopeimmin, mutta algoritmin kannalta oli välttämätöntä, että aika-arviot olisivat mahdollisimman tarkkoja. Algoritmia testattiin käyttämällä kyytejä ja hakuja, jotka vastasivat todellisia taksikyytejä. Tämä lähestymistapa otettiin sen takia, että Vedia Taxi ei ollut tuottanut tarpeeksi oikeaa testimateriaalia. Algoritmin tehokkuutta mitattiin samoilla testikyydeillä ja -hauilla. Testihaut näyttivät, että uusi algoritmi pystyy yhdistämään reittejä niin, että ihmiset lähtevät eri aloituspisteistä. Uusi algoritmi mahdollisti myös sen, että ihmiset pystyvät liittymään kyytiin matkan varrelta. Algoritmin tehokkuus oli suuresti riippuvainen siitä, kuinka pitkä aika kului reittiohjeiden laskemiseen. Reittiohjeiden laskeminen kulutti 92%-98% algoritmin kokonaissuoritusajasta. Reittiohjeiden haku kesti keskimäärin 275ms ja yhden kyydin arviointi hakua vastaan kesti 275-300ms. |
| Tiivistelmä (eng): | Vedia Taxi is a mobile application that makes it possible to share taxi rides with people going to the same direction. It uses an algorithm to combine the routes of different people to achieve this. However the algorithm can only handle cases where people leave from the same location and people cannot join from the route. The purpose of this work is to extend the algorithm to handle these cases. For the extended algorithm four routing services were compared. These routing services provide the raw route data and time estimates for the routes. Google Maps was chosen among these providers, because it had the most accurate time estimates for the routes. The raw routes from different providers had some differences, but all of them were adequate. While the Google Maps did not have the best route calculation time, it was crucial for the algorithm that the time estimates are as correct as they can be. The extended algorithm was tested using test searches that mimicked real life taxi rides, as there was not enough test data from real life rides made with the application. The performance of the algorithm was tested by using the same test searches. The test searches showcased that with the extended algorithm routes can be formed also when start locations are different. This also makes it possible to join along the route. The performance of the algorithm was highly dependant on the amount of time it took to calculate the raw routes. The calculation of routes took 92% and 98% of the running time of the algorithm. The average time to calculate raw route was 275ms and the evaluation of a single ride took 275-300ms. |
| ED: | 2016-11-13 |
INSSI tietueen numero: 55006
+ lisää koriin
INSSI