Development of route finding algorithm for dynamic ride sharing application

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Nordström, Miika
dc.contributor.author Päivinen, Jussi
dc.date.accessioned 2016-11-02T09:46:34Z
dc.date.available 2016-11-02T09:46:34Z
dc.date.issued 2016-10-27
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/23374
dc.description.abstract 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. en
dc.description.abstract 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. fi
dc.format.extent 54
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Development of route finding algorithm for dynamic ride sharing application en
dc.title Dynaamisen kyydinjakosovelluksen reitinhakualgoritmin kehitt äminen fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword sharing economy en
dc.subject.keyword taxi en
dc.subject.keyword routing en
dc.subject.keyword algorithms en
dc.identifier.urn URN:NBN:fi:aalto-201611025475
dc.programme.major Ohjelmistotekniikka fi
dc.programme.mcode T3001 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Malmi, Lauri
dc.programme Tietotekniikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account