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

završni rad

• Naslov (engleski): Solving the shortest path problem using a heuristic approach
• Autor: Nikolina Lovrić
• Mentor: Tomislav Erdelić (mentor)
• Član povjerenstva: Tonči Carić (predsjednik povjerenstva)
• Član povjerenstva: Pero Škorput (član povjerenstva)
• Član povjerenstva: Miroslav Vujić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet prometnih znanosti; (Inteligentni transportni sustavi i logistika); (Zavod za inteligentne transportne sustave); Zagreb
• Datum i država obrane: 2024-09-03, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Tehnologija prometa i transport; Inteligentni transportni sustavi i logistika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: najkraći put; optimizacija rute; C#; Dijkstra algoritam; A* algoritam; dvosmjerni algoritmi; heurističke metode; Fibonaccijeva hrpa
• Ključne riječi (engleski): shortest path; route optimization; C#; Dijkstra's algorithm; A* algorithm; bidirectional algorithms; heuristic methods; Fibonacci heap
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:119:786054
• Studijski program: Naziv: Inteligentni transportni sustavi i logistika; smjerovi: Inteligentni transportni sustavi, Logistika; Smjer: Inteligentni transportni sustavi; Vrsta studija: sveučilišni; Stupanj studija: prijediplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa (univ. bacc. ing. traff.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-12-06 14:11:47