Search academic texts

Information × Registration Number 2123U011469, Article popup.category Опубліковано, Стаття Title ON THE RECURSIVE ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM ON THE BASIS OF THE DATA FLOW OPTIMIZATION METHOD popup.author Івохін Є. В.Гавриленко В. В.Івохіна К.Є.Ivohin E. V.Gavrylenko V. V.Ivohina K. E. popup.publication 13-10-2023 popup.source_user Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") popup.source https://ric.zp.edu.ua/article/view/288143 popup.publisher National University "Zaporizhzhia Polytechnic" Description Актуальність. Важливою сучасною проблемою є швидке відновлення та оптимізація управління логістикою. В залежності від поставленої задачі існує багато різних математичних методів та підходів до вирішення різних логістичних задач, розв’язування яких набуває широкого практичного впровадження. Його конкретний зміст залежить від характеру проблеми та повноти наявних даних. Іноді для розв’язання відомих задач, однією з яких є задача комівояжера, вдається знайти нетипові методики на основі поєднання декількох обчислювальних схем та методів. Ціль. Мета роботи – розробити алгоритм розв’язання задачі комівояжера на основі реалізації методу потокового розподілу ресурсів і схеми backtracking з мінімальною тривалістю руху за маршрутом. Метод. У статті розглядається методика послідовного застосування потокових схем розподілу однорідного ресурсу для розв’язання задачі комівояжера, що формулюється як задача знаходження маршруту відвідування заданої кількості міст без повторень з мінімальною тривалістю руху. Поставлено та вирішено задачу формалізації алгоритму розв’язання проблеми комівояжера на основі методу розподілу ресурсів з використанням схеми backtracking. Запропоновано використання методу Орліна для оптимізації розподілу потоку на графі. Розроблено конструктивний алгоритм розв’язання задачі. Проведено обчислювальні експерименти. Результати. Розроблено метод розв’язання задачі комівояжера з використанням методу потокового розподілу ресурсів і схеми пошуку з поверненням. Запропоновано варіант прискорення швидкості розробленого алгоритму, яке полягає в залученні жадібного способу в процедурі вибору ділянок маршруту: планування кожного наступного етапу переміщення визначається виходячи з відбору найбільш швидкого напряму руху. Застосування жадібного підходу дозволило отримати конструктивну схему розв’язання задачі комівояжера. Представлено результати розрахунків за допомогою запропонованого алгоритму в задачах комівояжера з мінімізацією тривалості руху, проведено порівняння отриманих розв’язків з розв’язками, знайденими іншими точними та евристичними методами. Висновки. У статті розглянуто метод формалізації алгоритму розв’язання задачі комівояжера з використанням алгоритму потокового розподілу однорідного ресурсу та схеми backtracking. Запропоновано використання методу Орліна для оптимізації розподілу потоку на графі. Описано схему формалізації процедури використання методу з реалізацією схеми з поверненням для розв’язання задачі комівояжера з мінімізацією тривалості руху за маршрутом. Запропонований варіант прискорення роботи розробленого алгоритму. popup.nrat_date 2026-02-26 Close