ПОРІВНЯЛЬНИЙ АНАЛІЗ ЗАСТОСУВАННЯ ЕВРИСТИЧНИХ АЛГОРИТМІВ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ TSP

Анотація

Необхідність вирішення задачі комівояжера (TSP) часто виникає при вирішенні практично значущих оптимізаційних задач, таких як задачі в області економіки, логістики в найширшому діапазоні застосувань, в ланцюгах технічних програм. Досить часто специфіка цих задач вимагає отримання рішення, максимально наближеного до точного значення. Але задача TSP є NP-складною, тобто її точний розв’язок можна отримати лише за експоненціальний час. Тому розв’язувати задачу TSP за алгоритмом повного пошуку за наявності великої кількості вершин графа неефективно. Однак існують різноманітні евристичні алгоритми, які дозволяють знайти раціональне рішення цієї задачі з великою кількістю вершин за час, прийнятний для відповідної предметної області. У даній роботі задача комівояжера визначається як задача математичного програмування знаходження найкоротшого шляху руху комівояжера, метою якої є відвідування всіх об’єктів, задіяних у задачі в найкоротший термін і з мінімальними витратами. Відповідні адаптації евристичних алгоритмів, а саме генетичного алгоритму та алгоритму мурашиної колонії, розроблені в середовищі MATLAB. Проведено обчислювальний експеримент на вхідній вибірці, проведено порівняльний аналіз продуктивності двох евристичних алгоритмів і доведено ефективність використання евристичних алгоритмів для розв’язування NPкомплексних задач.