AZ UTAZÓ ÜGYNÖK PROBLÉMA MEGOLDÁSA METAHEURISZTIKUS ALGORITMUSOKKAL
Szerzők: POLYÁK Gabriella, doktorandusz, II. évfolyam1, tanársegéd2 (gabriellapolyak8@gmail.com), ORCID ID: 0009-0002-5102-1023
Intézmények: Újvidéki Egyetem, Műszaki Tudományok Kara, Közlekedési Szak, Újvidék1, Szabadkai Műszaki Szakfőiskola, Szabadka 2
A munka célkitűzése egy optimalizálási probléma megoldása metaheurisztikus módszerekkel. A probléma az utazó ügynök problémához hasonítható, ugyanis útvonal-optimalizációról van szó. A teszteléseket a Formula-1-es versenynaptár nagydíjhelyszíneinek földrajzi koordinátáin, valamint más, nyilvánosan elérhető adathalmazon végeztük el.
Az optimalizálás a Microsoft Excel egyik bővítményével, az Excel Solverrel történt, illetve MATLAB-ban íródott programokkal. A MATLAB-ban írt egyik program a genetikus algoritmusokban használt módszereket alkalmazza, mint amilyen a szelekció, mutáció, keresztezés és a visszahelyezés. A másik program pedig a hangyakolónia algoritmust alkalmazza, ami azon a természetbeli 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 munka összehasonlítja és összefoglalja a MATLAB és Excel használatával elért eredményeket.
Kulcsszavak: utazó ügynök probléma, útvonal-optimalizáció, metaheurisztikus algoritmusok, Formula-1
SOLVING THE TRAVELING SALESMAN PROBLEM WITH METAHEURISTIC ALGORITHMS
Authors: Gabriella POLYÁK, second-year PhD student 1, assistant 2, (gabriellapolyak8@gmail.com), ORCID ID: 0009-0002-5102-1023
Institutions: University of Novi Sad, Faculty of Technical Sciences, Traffic Engineering, Novi Sad1, Subotica Tech – College of Applied Sciences, Subotica2
The work’s objective is to use metaheuristic techniques to solve an optimization problem. Because it involves route optimization, the problem might be compared to the Traveling Salesman Problem. The physical coordinates of the Formula 1 Grand Prix locations and additional publicly accessible data sets were used for the testing.
Excel Solver, a Microsoft Excel add-in, and MATLAB programs were used for the optimization. Selection, mutation, crossover, and insertion are among the genetic algorithmic techniques utilized in one of the MATLAB applications. The ant colony algorithm (ACO) utilized by the other program is predicated on the innate notion that every ant leaves a trail, a specific chemical substance known as a pheromone; the more ants that travel the same path, the more pheromones there will be; this serves as “positive information” for each subsequent ant regarding the accuracy of a given path.
The paper compares and summarizes the results that were achieved using MATLAB and Excel.
Keywords: travelling salesman problem, route optimization, metaheuristic algorithms, Formula-1