ПОРІВНЯЛЬНЕ ДОСЛІДЖЕННЯ ДЕЯКИХ МЕТАЕВРИСТИЧНИХ АЛГОРИТМІВ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ КОМІВОЯЖЕРА

Application of the following three metaheuristic algorithms to Travelling Salesman Problem (TSP) were explored: Simulated Annealing (SA), Tabu Search (TS), and Ant Colony System (ACS). The performance of software implementation of these approaches was experimentally studied using four test instances of TSP with known optimal solutions. As a result of the experiment, features of solutions found in a set of trials by each algorithm in the same fixed amount of time were assessed. The
implementation details of the algorithms and the parameters used for the experiment were thoroughly described. Optimization process was visualized for every algorithm. Conclusions were made regarding the effectiveness of studied algorithms for the
different sizes of problem instances used in the experiment.

Досліджено застосування трьох метаевристичних алгоритмів для розв’язання задачі комівояжера: імітації відпалу, табу пошуку та мурашиної колонії. Проведено експериментальні дослідження продуктивності програмної реалізації алгоритмів на чотирьох тестових задачах комівояжера з відомими оптимальними маршрутами. В результаті експерименту оцінені характеристики розв’язків, отриманих кожним алгоритмом в серії вимірів за однакову фіксовану кількість часу. Детально описано застосовані в експерименті параметри алгоритмів і особливості реалізації. Візуалізова-
но процес оптимізації кожним із алгоритмів. Зроблено висновки щодо ефективності досліджених алгоритмів для різних розмірів задач, використаних у експерименті.