Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje

undergraduate thesis

• Title (english): Path finding optimization in a dynamic environment
• Author: Pavao Jerebić
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Nikolina Frid (član povjerenstva)
• Committee member: Marko Đurasević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Tema ovog rada je “Optimizacija pronalaženja najkraćeg puta uz dinamičko okruženje“. Problem je predstavljen u svijetu prometnih mreža i vozila koja se koja se njima gibaju. Prometna mreža je predstavljena grafom, a gužve su predstavljene kapacitetom kao težinama na bridovima. Pristup koji je odabran se sastoji od dviju komponenti. Prva komponenta je A* algoritam kojim se traži najkraći put u smislu prostorne udaljenosti između početne i krajnje točke. Drugi dio rješenja čini mravlji algoritam kojim to rješenje optimiziramo. Staza koja se dobije A* algoritmom služi za postavljanje početnog feromonskog traga gdje je trag jači što je taj čvor bliže cilju. Time je postignut efekt zatvarača koji se koristi i u stvarnim prometnim mrežama. Dobiveni rezultati su bili očekivani. Rješenja dobivena mravljim algoritmima su bila bolja od onih dobivenih samo A* algoritmom. Na manjim grafovima je dolazilo do utjecaja pristranosti najkraćem rješenju, ali je kod većih grafova bilo potrebno da bi se brzo pronašao neki put. Daljnjim iteracijama mravljeg algoritma, uspio se smanjiti taj utjecaj do zanemarive razine. Takvi rezultati su se na kraju pokazali dobrima i vidjelo se znatno poboljšanje od pohlepnog rješenja koje uzima u obzir samo najkraću udaljenost.

Abstract (english)

Subject of this thesis is „Path finding optimization in a dynamic environment“. The problem is presented in a traffic network environment with vehicles as object which are moving on said network. Traffic network is modeled with a graph and traffic jams are represented by capacities as weights on the edges of the graph. The chosen approach can be described with two components. The first component is A* algorithm that is used to find the shortest path, considering only space distance between the starting and the ending point. The second part is an ant algorithm which further optimizes given path. The path that is calculated with A* is used to set the initial pheromone trace where the closer the vertex is to the goal the higher the pheromone value will be. This achieved so called zipper effect, where two or more lanes merge at a later point, improving traffic flow. Results achieved were expected. Solutions calculated by ant algorithm were better then those calculated by only A* algorithm. There was some bias towards the shortest path on smaller graph which caused somewhat worse solutions, but on much bigger graphs that same bias helped to speed up ant algorithm search time. With further improving the optimization algorithm, negative effect on smaller graph was reduced to dismissably small levels. Such results have been shown to be satisfactory in the end and there was a significant improvement on the greedy algorithm where solutions were based only on the shortest space distance.

• Keywords: Pronalaženje puta; A*; evolucijsko računarstvo; inteligencija rojeva; optimizacija mravljim kolonijama; mravlji sustav; optimizacije prometa
• Keywords (english): Path finding; A* algorithm; Evolutionary computing; Swarm intelligence; Ant colony optimizations; Ant system; Traffic optimizations
• Language: croatian
• URN:NBN: urn:nbn:hr:168:204158
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 21:13:04