Path finding optimization in a dynamic environment

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.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