Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (rajattu näkyvyys)
  • Näytä aineisto
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (rajattu näkyvyys)
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Reitinsuunnittelualgoritmien vertailu karttaympäristössä

Ruostetsaari, Jose (2025-06-05)

Reitinsuunnittelualgoritmien vertailu karttaympäristössä

Ruostetsaari, Jose
(05.06.2025)
Katso/Avaa
Ruostetsaari_Jose_opinnayte.pdf (1.545Mb)
Lataukset: 

Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
suljettu
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2025070477662
Tiivistelmä
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.
 
Kokoelmat
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (rajattu näkyvyys) [5164]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste