aalto1 untyped-item.component.html
Evaluating Modern Shortest Path Algorithms on Finnish Road Networks
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Language
en
Pages
77
Series
Abstract
The shortest path problem is a fundamental computational challenge with extensive applications in the field of route planning, in which obtaining effective routes relies on performant shortest path algorithms. Due to the importance of various route planning applications, from navigators to delivery route optimizers, shortest path algorithms for road networks have recently experienced rapid advancements. These developments employ diverse indexing techniques to create auxiliary speedup structures, enabling solutions that are orders of magnitude faster than classical, non-indexing-based approaches.
This work investigates the performances and other characteristics of these modern shortest path algorithms within the context of Finnish road networks, an area that has not been previously explored in an evaluative study. The evaluations conducted focus on three modern shortest path algorithms, Contraction Hierarchies (CH), Customizable Contraction Hierarchies (CCH), and Transit Node Routing (TNR), applied to increasingly sized Finnish road networks. Based on the results, these algorithms are compared both against one another and against four classical shortest path algorithms also evaluated in this study. Additionally, to this comparative analysis, the suitability of the evaluated algorithms for solving the shortest path problem in Finnish road networks is assessed.
Overall, the modern approaches exhibit significantly improved performance over classical algorithms, with the most substantial gains observed in larger evaluation areas. In the evaluations, ranging from the road network of Uusimaa to the entire road network of Finland, the modern algorithms achieve speedups of two to three orders of magnitude compared to classical methods. Coupled with relatively fast preprocessing times and small speedup structure sizes offered by some of the evaluated algorithms, these findings strongly advocate the use of modern shortest path algorithms in the road networks of Finland.
Lyhimmän polun ongelma (engl. the shortest path problem) on keskeinen laskennallinen haaste, jolla on laajat sovellukset reittisuunnittelun alalla, jossa tehokkaiden reittien löytäminen perustuu suorituskykyisiin lyhimmän polun algoritmeihin. Erilaisten reitinsuunittelusovellusten tärkeyden, aina navigaattoreista toimitusreittien optimoijiin, vuoksi lyhimmän polun algoritmit ovat lähiaikoina ottaneet nopeita edistysaskeleita. Nämä kehitysaskeleet hyödyntävät erilaisia indeksointitekniikoita luodakseen nopeutusrakenteita, jotka puolestaan mahdollistavat monta kertaluakkaa nopeamman suorituskyvyn klassisiin ei nopeutusrakenteita hyödyntäviin algorithmeihin verrattuna.
Tässä työssä tutkitaan näiden modernien lyhimmän polun algoritmien suorituskykyä ja muita ominaisuuksia Suomen tieverkoissa, jota alueena ei ole käsitelty aikaisemmissa moderneja algoritmeja arvioivissa tutkimuksissa. Työssä suoritetut arvioinnit keskittyvät kolmeen moderniin lyhimmän polun algoritmiin, supistamishierarkioihin (engl. Contraction Hierarchies), muokattaviin supistamishierarkioihin (engl. Customizable Contraction Hierarchies) ja vaihtosolmureititykseen (engl. Transit Node Routing), joita kaikkia sovelletaan kasvavan kokoisiin Suomen tieverkkoihin. Saatujen tulosten perusteella kyseisiä algoritmeja vertaillaan sekä keskenään että myös neljän klassisen lyhimmän polun algoritmin kanssa, jotka tässä työssä myös arvioidaan. Tämän vertailevan analysoinnin ohella, työ myös arvioi kyseisten algoritmien soveltuvuutta lyhimmän polun ongelman ratkaisemiseen Suomen tieverkoissa.
Yleistäen modernien menetelmien todetaan yltävän merkittävästi klassisia algoritmeja parempaan suorituskykyyn, erityisesti suuremmilla testialulueilla. Työn arvioinneissa, jotka kattavat tieverkot Uudenmaan tieverkosta aina koko Suomen tieverkkoon, modernit algoritmit saavuttavat kahdesta kolmeen kertaluokan nopeutuksen verrattuna klassisiin menetelmiin. Tämän ohella joidenkin arvioitujen algoritmien melko nopeiden ennakkokäsittelyaikojen ja pientedn nopeuttamisrakenteiden kokojen vuoksi, kyseisten algorithmien käyttö Suomen tieverkoissa nouseekin erittäin suositeltavaksi.