Евристичний підхід до програмної реалізації методу Літтла на прикладі задачі комівояжера

Abstract

У статті розглянуто задачу комівояжера (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP), яка є однією з найвідоміших та найважливіших оптимізаційних задач у теорії графів та прикладній математиці. Вона має широке практичне застосування, включаючи логістику, планування маршрутів та управління ресурсами. Суть задачі полягає у пошуку найвигіднішого маршруту, що проходить через задані міста лише один раз, а потім повертається до початкової точки. В умовах даної задачі застосовуються критерій вигідності маршруту (тобто найкоротший та найдешевший маршрут) і відповідні матриці відстаней (в кілометрах), тобто основна мета - мінімізувати загальну довжину маршруту або його вартість. Задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів. Для можливості застосування математичного апарату для розв'язання проблеми, її представлено у вигляді математичної моделі. Проблему комівояжера формулюють у вигляді моделі на графі, де міста представлені як вершини, а відстані між ними - як ребра. Авторами запропоновано застосування евристичного методу до розв’язання даної задачі. Для цього вдосконалено програмну реалізацію алгоритму Літтла, який вибирає для розбиття множини з мінімальною межею з усіх можливих гілок, а не з двох отриманих в результаті останнього розбиття. При цьому використовується евристичний підхід до вибору множини з межею не більше, ніж мінімальна. Продемонстровано роботу програми на прикладі проїзду автомобілем між містами України, заданими реальної матрицею відстаней (в кілометрах). У статті розглянуто модернізований метод Літтла для розв’язання задачі комівояжера, що демонструє значно вищу швидкість роботи порівняно з методом повного перебору. Основна ідея - використання евристичного підходу для скорочення простору пошуку та зниження витрат ресурсів. Тестування на прикладі міст України з використанням реальної матриці відстаней у кілометрах підтвердило ефективність алгоритму, який обирає оптимальні розв’язання, зберігаючи мінімальні межі витрат.

The article deals with the Traveling Salesman Problem (TSP), which is one of the most famous and important optimization problems in graph theory and applied mathematics. It has a wide range of practical applications, including logistics, route planning and resource management. The essence of the problem is to find the most profitable route that passes through the given cities only once and then returns to the starting point. In the conditions of this problem, the route profitability criterion (that is, the shortest and cheapest one) and the corresponding distance matrices (in kilometers) are used, that is, the main goal is to minimize the total length of the route or its cost. It is given that the route should pass through each city only once, in this case the intersection is among the Hamiltonian cycles. For the possibility of applying the mathematical apparatus to solve the problem, it is presented in the form of a mathematical model. The Traveling Salesman Problem is formulated in the form of a model on a graph, where cities are represented as vertices, and the distances between them are represented as edges. The authors proposed the use of a heuristic method to solve this problem. For this, the software implementation of Little's algorithm has been improved, which selects for partitioning a set with the minimum limit from all possible branches, and not from the two obtained as a result of the last partition. At the same time, a heuristic approach is used to select a set with a limit no greater than the minimum. The work of the program is demonstrated on the example of driving between cities of Ukraine, given by the real matrix of distances (in kilometers). The article considers the modernized Little method for solving the Traveling Salesman Problem, which demonstrates a significantly higher speed of work compared to the method of complete search. The main idea is to use a heuristic approach to reduce the search space and reduce resource costs. Testing on the example of cities of Ukraine using a real matrix of distances in kilometers confirmed the effectiveness of the algorithm, which selects optimal solutions while saving minimum cost limits.