Problem rješavanja najkraćeg puta koristeći heuristički pristup

undergraduate thesis

• Title (english): Solving the shortest path problem using a heuristic approach
• Author: Nikolina Lovrić
• Mentor: Tomislav Erdelić (mentor)
• Committee member: Tonči Carić (predsjednik povjerenstva)
• Committee member: Pero Škorput (član povjerenstva)
• Committee member: Miroslav Vujić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Transport and Traffic Sciences; (Division of Intelligent Transport Systems and Logistics); (Department of Intelligent Transport Systems); Zagreb
• Defense date and country: 2024-09-03, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Traffic and Transport Technology; Intelligent Transport Systems and Logistics

Abstract

U ovom završnom radu proučava se primjena heurističkih pristupa za rješavanje
problema najkraćeg puta na cestovnoj mreži Hrvatske. Glavni cilj je optimizacija pronalaska
najkraćih ruta korištenjem prikupljenih podataka o stanju cestovne mreže i rješavanje najkraćeg
puta koristeći algoritme kao što su A* i Dijkstrin algoritam, te njihove dvosmjerne verzije i
verzije unaprijeđene Fibonaccijevom hrpom. Podatci prikupljeni putem projekta SORDITO
detaljno su obrađeni u programskom jeziku C#, uključujući digitalnu kartu cestovne mreže s
jedinstvenim ID-ovima, koordinatama, ograničenjima brzine i kategorijama. Rad se detaljno
bavi analizom učinkovitosti različitih algoritama za rješavanje najkraćeg puta te opisuje razvoj
grafičkog sučelja u Visual Studio-u. Ovo sučelje omogućuje korisnicima interaktivni prikaz
optimiziranih ruta i relevantnih podataka, čime se olakšava pregled i razumijevanje rezultata u
stvarnom vremenu. Ovaj projekt ističe važnost heurističkih metoda u optimizaciji transportnih
sustava, pružajući praktična rješenja za složene grafove poput cestovne mreže Hrvatske.

Abstract (english)

This final thesis explores the application of heuristic approaches to solving the shortest
path problem on the road network of Croatia. The main objective is to optimize the
determination of shortest routes using collected data on the state of the road network and
algorithms such as A* and Dijkstra's algorithm, as well as their bidirectional versions enhanced
by Fibonacci heap. Data gathered through the SORDITO project have been extensively
processed using the C# programming language, including the digital map of the road network
with unique IDs, coordinates, speed limits, and categories. The thesis extensively analyzes the
efficiency of different shortest path algorithms and describes the development of a graphical
user interface in Visual Studio. This interface enables users to interactively visualize optimized
routes and relevant data, facilitating real-time review and understanding of results. This project
highlights the importance of heuristic methods in optimizing transportation systems, providing
practical solutions for complex graphs such as Croatia's road network.

• Keywords: najkraći put; optimizacija rute; C#; Dijkstra algoritam; A* algoritam; dvosmjerni algoritmi; heurističke metode; Fibonaccijeva hrpa
• Keywords (english): shortest path; route optimization; C#; Dijkstra's algorithm; A* algorithm; bidirectional algorithms; heuristic methods; Fibonacci heap
• Language: croatian
• URN:NBN: urn:nbn:hr:119:786054
• Study programme: Title: Intelligent Transportation Systems and Logistics; specializations in: Intelligent Transportation Systems, Logistics; Course: Intelligent Transportation Systems; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-12-06 14:11:47