Search academic texts

Information × Registration Number 2124U002667, Article popup.category Стаття, Опубліковано, Рецензована стаття Title COMPARATIVE ANALYSIS OF THE APPLICATION OF HEURISTIC ALGORITHMS FOR SOLVING THE TSP PROBLEM popup.author Skakalina О.Kapiton A.Skakalina O.Kapiton A. popup.publication 30-04-2024 popup.source_user Національний університет «Полтавська політехніка імені Юрія Кондратюка» popup.source https://journals.nupp.edu.ua/sunz/article/view/3371 popup.publisher Національний університет «Полтавська політехніка імені Юрія Кондратюка» Description Необхідність вирішення задачі комівояжера (TSP) часто виникає при вирішенні практично значущих оптимізаційних задач, таких як задачі в області економіки, логістики в найширшому діапазоні застосувань, в ланцюгах технічних програм. Досить часто специфіка цих задач вимагає отримання рішення, максимально наближеного до точного значення. Але задача TSP є NP-складною, тобто її точний розв’язок можна отримати лише за експоненціальний час. Тому розв’язувати задачу TSP за алгоритмом повного пошуку за наявності великої кількості вершин графа неефективно. Однак існують різноманітні евристичні алгоритми, які дозволяють знайти раціональне рішення цієї задачі з великою кількістю вершин за час, прийнятний для відповідної предметної області. У даній роботі задача комівояжера визначається як задача математичного програмування знаходження найкоротшого шляху руху комівояжера, метою якої є відвідування всіх об’єктів, задіяних у задачі в найкоротший термін і з мінімальними витратами. Відповідні адаптації евристичних алгоритмів, а саме генетичного алгоритму та алгоритму мурашиної колонії, розроблені в середовищі MATLAB. Проведено обчислювальний експеримент на вхідній вибірці, проведено порівняльний аналіз продуктивності двох евристичних алгоритмів і доведено ефективність використання евристичних алгоритмів для розв’язування NPкомплексних задач. popup.nrat_date 2026-04-19 Close