Reitinsuunnittelualgoritmien vertailu karttaympäristössä

Abstract

Tässä diplomityössä on vertailtu A*-, reunahaku-, Dijkstra- ja kaksisuuntainen Dijkstra- algoritmeja karttapohjaisessa reitinsuunnittelussa. Karttapohjana on käytetty pythonin OSMnx-kirjastoa. Kartta-alueina on käytetty Suomen kaupunkeja sekä maanteitä. Tutkimuksessa mitattiin näiden algoritmien löytämien polkujen pituudet sekä niiden käyttämä aika ja muisti. Mittaukset suoritettiin kahdesti samalle alku- ja loppupisteelle, mutta toisella kerralla lyhimmän polun varrelle oli asetettu tiesulku. Tällöin algoritmi joutuu etsimään uuden vaihtoehtoisen reitin. Tutkimuksessa vertailtiin algoritmien muistin- ja ajankäytön tehokkuutta. Yleisen tehokkuuden määrittämiseksi muistin- ja ajankäytön tehokkuudet on normalisoitu ja painotettu saman arvoisiksi, jonka jälkeen ne on summattu yhteen. Tutkimustuloksista huomataan, ettei tiesululla ollut suurempaa vaikutusta algoritmien tehokkuuteen. Algoritmien välillä on eroavaisuuksia kaupungissa ja maantiellä. Kaupungissa kaksisuuntainen Dijkstra on tehokkain algoritmi. Maantiellä, sekä yleisesti kaikki tutkimusdata huomioiden, reunahaku suoriutuu keskimääräisesti parhaiten. A* ei ollut missään tehokkain, mutta sen muistin- ja ajankäytön tehokkuus oli toisiksi paras jokaisessa testissä. Dijkstra suoriutui tutkimuksessa heikoiten. Algoritmien välillä on siis eroja, mutta todellisuudessa puhutaan sekunnin murto-osista ja muutaman MB:n eroavaisuuksista.

This diploma thesis compares the A*, Fringe Search, Dijkstra, and Bidirectional Dijkstra algorithms in map-based path planning. The map data is based on the Python OSMnx library. The map areas consist of Finnish cities and highways. The study measured the length of the paths found by the algorithms, as well as their time and memory usage. Each test was performed twice using the same start and end points. However, in the second test, a roadblock was placed along the shortest path, forcing the algorithm to find an alternative route. The study focused on comparing the time and memory efficiency of the algorithms. To determine overall efficiency, time and memory metrics were normalized and weighted equally, after which they were summed together. The results indicate that the roadblock had no significant impact on algorithm performance. Differences were observed between the algorithms depending on whether the environment was city or highway. In cities, the Bidirectional Dijkstra algorithm was the most efficient. On highways and when considering all the test data as a whole Fringe Search achieved the best average performance. A was never the most efficient, but its time and memory usage consistently ranked second-best in all tests. Dijkstra performed the weakest overall. Although there are measurable differences between the algorithms, in practice the variations amount to fractions of a second and a few megabytes of memory.