Útvonaltervezés heurisztikus módszerekkel –a hangyakolónia algoritmus

Abstract

A munka célja egy útvonaltervezési probléma megoldása heurisztikus módszerrel. A problémát lehet az utazó ügynök problémához hasonítani, ugyanis útvonaltervezésről, illetve útvonal optimalizációról van szó. A munka alapját a Formula-1-es versenynaptár nagydíjhelyszíneinek földrajzi koordinátái képezik, azonban bármilyen más, nyilvánosan elérhető adathalmazon is futtatni lehet a programokat. A munkában a Microsoft Excel egyik bővítménye, az Excel Solver lett használva, illetve egy MATLAB-ban íródott program, ami a hangyakolónia algoritmust alkalmazza. A hangyakolónia algoritmus azon a természetbeni megfigyelésen alapul, hogy minden hangya nyomot hagy maga után, egy bizonyos feromon nevű vegyi anyagot, és minél több hangya követi ugyanazt az utat, annál több a lesz a feromon, és ez minden következő hangyának "pozitív információ" az adott út helyességéről. A munkában az Excelben és a MATLAB-ban kapott eredmények kerülnek összehasonlításra és összegzésre.

The aim of this paper is to solve a route planning problem using a heuristic method. The problem can be compared to the traveling salesman problem, because it is about route planning and route optimization. The basis of the work is the geographical coordinates of the grand prix locations of the Formula 1 race calendar, but the programs can also be run on any other publicly available data set. An extension of Microsoft Excel, Excel Solver, was used in the paper, as well as a program written in MATLAB, which uses the ant colony algorithm. The ant colony algorithm is based on the natural observation that each ant leaves a trail, a certain chemical substance called a pheromone, and the more ants follow the same path, the more pheromone will be, and this is "positive information" for each subsequent ant. about the correctness of a given road. In this work, the results obtained in Excel and MATLAB are compared and summarized.