Задача Комівояжера

Йосипчук А, І. Задача Комівояжера : випускна кваліфікаційна робота бакалавра : 113 Прикладна математика / Йосипчук Анастасія Ігорівна. – Київ, 2023. – 37 с.

Метою дипломної роботи є дослідження і розв'язання задачі Комівояжера з метою знайти оптимальний маршрут та реалізувати для цього ефективний алгоритм з мінімальними обчислювальними витратами, використовуючи стандартний технічний пристрій.
В роботі було розглянуто історію виникнення задачі Комівояжера, її теоретичну постановку, задачі, що зводяться до неї (Гамільтона, Переналадка станків) а також точні та наближені алгоритми розв’язання (алгоритм повного перебору, гілок та меж, алгоритм найближчого сусіда, алгоритм випадкових чисел, генетичний алгоритм, мурашиний алгоритм, k-opt алгоритм) та оцінку якості їх виконання.
Було реалізовано вибірково 4 з них: алгоритм повного перебору, алгоритм найближчого сусіда, генетичний алгоритм, k-opt, та візуалізовані результати за допомогою бібліотеки Python folium. В результаті було побудувано наближений до оптимального маршрут та проаналізовано роботу алгоритмів на прикладі використаної задачі.