Юрчишин, Василь ЯковичМаховой, Олександр Вікторович2025-10-152025-10-152024Маховой, М. В. Спосіб та програмне забезпечення для оптимізації маршрутів комівояжера : магістерська дис. : 121 Інженерія програмного забезпечення / Маховой Олександр Вікторович. – Київ, 2024. – 162 с.https://ela.kpi.ua/handle/123456789/76868На сьогодні задача комівояжера є однією з ключових у галузі комбінаторної оптимізації, яка знаходить застосування у таких сферах, як логістика, планування маршрутів, навігація та інші. Незважаючи на численні існуючі алгоритми, проблема ефективного вирішення задачі для великих наборів даних з нерівномірним розподілом точок залишається актуальною. У даній роботі запропоновано новий комбінований підхід до розв’язання задачі комівояжера, що поєднує геометричну евристику та локальну оптимізацію. Основна ідея полягає у побудові початкового маршруту на основі крайніх точок (північ, південь, захід, схід) із подальшою динамічною обробкою відкритих міст за допомогою черги пріоритетів і багатокрокової реінсерції для локальної оптимізації маршруту. Такий підхід забезпечує покращення довжини маршруту в середньому на 2,91%, а на окремих наборах даних — до 4,30% у порівнянні з кращими аналогами. Для реалізації розробленого методу створено десктопний застосунок з використанням мови програмування C#, фреймворків WPF, OxyPlot, що дозволяє виконувати інтерактивне моделювання, візуалізацію та оптимізацію маршрутів. Результати дослідження підтверджують високу ефективність запропонованого алгоритму та його потенціал для застосування у практичних сценаріях, таких як транспортна логістика, оптимізація поставок та інші завдання маршрутизації.162 с.ukзадача комівояжераоптимізаціякористувацький алгоритммаршрутлокальна оптимізаціяоптимізація повторної вставкикомбінаторна оптимізаціяпрограмне забезпеченняMaster Thesis004.023