An Analysis of the Effectiveness of Heuristic Algorithms for Solving the Traveling Salesman Problem

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.