2023, випуск 4, c. 43-52
Одержано 21.11.2023; Виправлено 27.11.2023; Прийнято 28.11.2023
Надруковано 04.12.2023; Вперше Online 05.12.2023
https://doi.org/10.34229/2707-451X.23.4.6
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Природний підхід до розв'язання задачі комівояжера
Д.Г. Терзі 
Державний університет Молдови, Кишинів
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Задача комівояжера відноситься до задач транспортного типу. Природно до її розв'язання застосувати метод, заснований на технології розв'язування транспортних задач. Циклічність і виродженість розв'язку задачі комівояжера вимагає суттєвої модифікації відповідних етапів розв'язування транспортної задачі (складання початкового допустимого розв'язку; перевірка плану на оптимальність; отримання нового допустимого розв'язку).
Мета роботи. Розробка природного підходу до розв'язання задачі комівояжера. Опис структури множини задач комівояжера, що мають заданий наперед оптимальний розв'язок. Алгоритмічне формування таких задач із проведенням масових обчислювальних експериментів.
Результати. У роботі представлені нові результати та обчислювальні експерименти з розробленим природним алгоритмом розв'язання задачі комівояжера, заснованим на технології розв'язування транспортних задач, що включає новий ефективний спосіб генерації початкового циклічного розв'язку, алгоритм переходу від початкового циклічного до іншого. Розроблено алгоритм побудови задачі комівояжера із заданим наперед оптимальним розв'язком, що сприяє кращому розумінню структури задач комівояжера.
Висновки. Результати обчислювальних експериментів показують, що використання технології методу потенціалів для розв'язання задачі комівояжера, як спеціальної транспортної задачі, є перспективним напрямом пошуку якісного розв'язку. Розроблені алгоритми та програми розширюють можливості розв'язання задачі комівояжера. Час розв'язання задачі суттєво залежить від розмірності задачі. У цьому плані істотним є автоматичне формування задачі комівояжера із заданим оптимальним розв'язком, що дозволяє проводити масові експерименти та зробити висновки.
Ключові слова: задача комівояжера, метод потенціалів, критерій оптимальності, циклічна підстановка, маршрут, алгоритм.
Цитувати так: Terzi D. A Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2023. 4. P. 43–52. https://doi.org/10.34229/2707-451X.23.4.6
Список літератури
1. Grötschel M. The Travelling Salesman Problem and its Applications. Combinatorial Optimization at Work. Block Course at TU Berlin, October 4 – 15, 2005. https://co-at-work.zib.de/berlin/download/CD/Talks/02M1-TSP.pdf
2. Taillard E.D. Design of Heuristic Algorithms for Hard Optimization, With Python Codes for the Travelling Salesman Problem. Springer, 2023. https://doi.org/10.1007/978-3-031-13714-3
3. Roberti R., Toth P. Models and algorithms for the Asymmetric Traveling Salesman Problem: An experimental comparison. EURO Journal on Transportation and Logistics. 2012. 1 (1–2). P. 113–133. https://doi.org/10.1007/s13676-012-0010-0
4. Hasan-Shawopn M.F., Raval N. Operations research: Traveling Salesman Problem. Technical Report. Wernigerode, Germany, 2023. 57 p. https://www.researchgate.net/publication/369973661
5. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. 382 с.
6. Sharma J.K. Operations Research: Theory and Applications. Macmillan Publishers India Limited, 2009. 976 p. https://books.google.com.ua/books?id=1EZxJHO32swC
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна