Analýza efektivity heuristických algoritmů při řešení problému obchodního cestujícího
Autor(ka) práce:
Hardy, Oliver
Typ práce:
Bakalářská práce
Vedoucí práce:
Čížková, Šárka
Oponenti práce:
Vávra, Vojtěch
Jazyk práce:
Česky
Abstrakt:
Tato bakalářská práce se zabývá porovnáním efektivity vybraných heuristických a exaktních metod při řešení symetrického euklidovského problému obchodního cestujícího. Cílem práce je posoudit praktickou použitelnost algoritmů 2-opt, 3-opt, Simulated Annealing a genetického algoritmu v prostředí Pythonu, a to z hlediska kvality nalezeného řešení, výpočetního času a škálovatelnosti. Jako referenční exaktní metoda je použit solver Concorde, který slouží k určení optimálních hodnot pro výpočet relativní odchylky heuristických řešení od optima. Experimenty jsou provedeny na vybraných instancích z knihovny TSPLIB a na náhodně generovaných euklidovských instancích různých velikostí. Heuristické algoritmy jsou testovány ve dvou inicializačních režimech: s náhodnou inicializací a s inicializací pomocí metody nejbližšího souseda. Výsledky ukazují, že nejnižší relativní odchylky od optima dosahoval algoritmus Simulated Annealing, který zároveň poskytoval nejlepší kompromis mezi kvalitou řešení a výpočetním časem. Algoritmy 2-opt a 3-opt byly výrazně rychlejší, ale dosahovaly horší kvality řešení. Nearest-neighbour inicializace významně zlepšila výsledky algoritmů 2-opt, 3-opt a genetického algoritmu, zatímco u Simulated Annealing byl její vliv minimální. Genetický algoritmus v použitém nastavení vykazoval zejména při náhodné inicializaci vysokou variabilitu a horší škálovatelnost.
An Analysis of the Effectiveness of Heuristic Algorithms for Solving the Traveling Salesman Problem
Autor(ka) práce:
Hardy, Oliver
Typ práce:
Bachelor thesis
Vedoucí práce:
Čížková, Šárka
Oponenti práce:
Vávra, Vojtěch
Jazyk práce:
Česky
Abstrakt:
This bachelor thesis compares the effectiveness of selected heuristic and exact methods for solving the symmetric Euclidean travelling salesman problem. The aim of the thesis is to evaluate the practical applicability of the 2-opt, 3-opt, Simulated Annealing and genetic algorithm implementations in Python, with respect to solution quality, computational time and scalability. The Concorde solver is used as an exact reference method to obtain optimal values for calculating the relative deviation of heuristic solutions from the optimum. The experiments are carried out on selected TSPLIB benchmark instances and on randomly generated Euclidean instances of different sizes. The heuristic algorithms are tested under two initialization strategies: random initialization and nearest-neighbour initialization. The results show that Simulated Annealing achieved the lowest relative deviations from the optimum and provided the best compromise between solution quality and computational time. The 2-opt and 3-opt algorithms were substantially faster, but their solution quality was lower. Nearest-neighbour initialization significantly improved the results of 2-opt, 3 opt and the genetic algorithm, while its effect on Simulated Annealing was minimal. In the tested configuration, the genetic algorithm showed high variability and weaker scalability, especially under random initialization.