On the recursive algorithm for solving the traveling salesman problem on the basis of the data flow optimization method

Abstract

EN: Context. The article considers a technique for the sequential application of flow schemes for distributing a homogeneous re-source for solving the traveling salesman problem, which is formulated as the problem of finding a route to visit a given number of cities without repetitions with a minimum duration of movement. The task of formalizing the algorithm for solving the traveling salesman problem by the method of streaming resource distribution using the backtracking scheme is posed. The use of Orlin’s method to optimize the flow distribution on the graph is proposed. Objective. The goal of the work is to develop an algorithm for solving the traveling salesman problem based on the implementation of the method of streaming resource distribution and the backtracking scheme with the minimum duration of movement along the route. Method. This paper proposes a method for solving the traveling salesman problem by the method of streaming resource distribution with the backtracking scheme. A scheme for formalizing the procedure for solving the traveling salesman problem with the minimum duration of movement along the route is described. A variant of accelerating the speed of the developed algorithm is proposed, which consists in using a greedy technique in the procedure for selecting route sections: planning each subsequent stage of movement is determined based on the choice of the fastest direction of movement. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the duration of movement are presented, the obtained solutions are compared with the solutions found by other exact and heuristic methods. Results. The method for solving the traveling salesman problem using the method of streaming resource allocation and using the backtracking scheme is developed. A variant of accelerating the speed of the developed algorithm is proposed, which consists in using a greedy technique in the procedure for selecting route sections: planning each subsequent stage of movement is determined based on the choice of the fastest direction of movement. The application of the greedy approach makes it possible to obtain a constructive scheme for solving the traveling salesman problem. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the duration of movement are presented, the obtained solutions are compared with the solutions found by other exact and heuristic methods. Conclusions. The paper considers a method for formalizing the algorithm for solving the traveling salesman problem using the method of streaming resource allocation and the backtracking scheme. The use of Orlin’s method to optimize the flow distribution on the graph is proposed. The scheme of formalization of the procedure for using the method with the implementation of the backtracking scheme for solving the traveling salesman problem with the minimum duration of movement along the route is briefly described. A variant of accelerating the speed of the developed algorithm is proposed. UK: Актуальність. Важливою сучасною проблемою є швидке відновлення та оптимізація управління логістикою. В залежності від поставленої задачі існує багато різних математичних методів та підходів до вирішення різних логістичних задач, розв’язування яких набуває широкого практичного впровадження. Його конкретний зміст залежить від характеру проблеми та повноти наявних даних. Іноді для розв’язання відомих задач, однією з яких є задача комівояжера, вдається знайти нетипові методики на основі поєднання декількох обчислювальних схем та методів. Ціль. Мета роботи – розробити алгоритм розв’язання задачі комівояжера на основі реалізації методу потокового розподілу ресурсів і схеми backtracking з мінімальною тривалістю руху за маршрутом. Метод. У статті розглядається методика послідовного застосування потокових схем розподілу однорідного ресурсу для розв’язання задачі комівояжера, що формулюється як задача знаходження маршруту відвідування заданої кількості міст без повторень з мінімальною тривалістю руху. Поставлено та вирішено задачу формалізації алгоритму розв’язання проблеми комівояжера на основі методу розподілу ресурсів з використанням схеми backtracking. Запропоновано використання методу Орліна для оптимізації розподілу потоку на графі. Розроблено конструктивний алгоритм розв’язання задачі. Проведено обчислювальні експерименти. Результати. Розроблено метод розв’язання задачі комівояжера з використанням методу потокового розподілу ресурсів і схеми пошуку з поверненням. Запропоновано варіант прискорення швидкості розробленого алгоритму, яке полягає в залученні жадібного способу в процедурі вибору ділянок маршруту: планування кожного наступного етапу переміщення визначається виходячи з відбору найбільш швидкого напряму руху. Застосування жадібного підходу дозволило отримати конструктивну схему розв’язання задачі комівояжера. Представлено результати розрахунків за допомогою запропонованого алгоритму в задачах комівояжера з мінімізацією тривалості руху, проведено порівняння отриманих розв’язків з розв’язками, знайденими іншими точними та евристичними методами. Висновки. У статті розглянуто метод формалізації алгоритму розв’язання задачі комівояжера з використанням алгоритму потокового розподілу однорідного ресурсу та схеми backtracking. Запропоновано використання методу Орліна для оптимізації розподілу потоку на графі. Описано схему формалізації процедури використання методу з реалізацією схеми з поверненням для розв’язання задачі комівояжера з мінімізацією тривалості руху за маршрутом. Запропонований варіант прискорення роботи розробленого алгоритму.