Спосіб та програмне забезпечення для оптимізації маршрутів комівояжера

Скорочена інформація про документ
dc.contributor.advisorЮрчишин, Василь Якович
dc.contributor.authorМаховой, Олександр Вікторович
dc.date.accessioned2025-10-15T09:52:48Z
dc.date.available2025-10-15T09:52:48Z
dc.date.issued2024
dc.description.abstractНа сьогодні задача комівояжера є однією з ключових у галузі комбінаторної оптимізації, яка знаходить застосування у таких сферах, як логістика, планування маршрутів, навігація та інші. Незважаючи на численні існуючі алгоритми, проблема ефективного вирішення задачі для великих наборів даних з нерівномірним розподілом точок залишається актуальною. У даній роботі запропоновано новий комбінований підхід до розв’язання задачі комівояжера, що поєднує геометричну евристику та локальну оптимізацію. Основна ідея полягає у побудові початкового маршруту на основі крайніх точок (північ, південь, захід, схід) із подальшою динамічною обробкою відкритих міст за допомогою черги пріоритетів і багатокрокової реінсерції для локальної оптимізації маршруту. Такий підхід забезпечує покращення довжини маршруту в середньому на 2,91%, а на окремих наборах даних — до 4,30% у порівнянні з кращими аналогами. Для реалізації розробленого методу створено десктопний застосунок з використанням мови програмування C#, фреймворків WPF, OxyPlot, що дозволяє виконувати інтерактивне моделювання, візуалізацію та оптимізацію маршрутів. Результати дослідження підтверджують високу ефективність запропонованого алгоритму та його потенціал для застосування у практичних сценаріях, таких як транспортна логістика, оптимізація поставок та інші завдання маршрутизації.
dc.description.abstractotherToday, the traveling salesman problem is one of the key problems in combinatorial optimization, which is used in such areas as logistics, route planning, navigation, and others. Despite the numerous existing algorithms, the problem of efficiently solving the problem for large datasets with uneven distribution of points remains relevant. In this paper, we propose a new combined approach to solving the traveling salesman problem that combines geometric heuristics and local optimization. The main idea is to build an initial route based on the endpoints (north, south, west, east), followed by dynamic processing of open cities using a priority queue and multi-step reinsertion for local route optimization. This approach improves the route length by an average of 2.91%, and on some datasets - up to 4.30% compared to the best analogs. To implement the developed method, a desktop application was created using the C# programming language, WPF, and OxyPlot frameworks, which allows for interactive modeling, visualization, and route optimization. The results of the study confirm the high efficiency of the proposed algorithm and its potential for application in practical scenarios such as transport logistics, supply optimization, and other routing tasks.
dc.format.extent162 с.
dc.identifier.citationМаховой, М. В. Спосіб та програмне забезпечення для оптимізації маршрутів комівояжера : магістерська дис. : 121 Інженерія програмного забезпечення / Маховой Олександр Вікторович. – Київ, 2024. – 162 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/76868
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectзадача комівояжера
dc.subjectоптимізація
dc.subjectкористувацький алгоритм
dc.subjectмаршрут
dc.subjectлокальна оптимізація
dc.subjectоптимізація повторної вставки
dc.subjectкомбінаторна оптимізація
dc.subjectпрограмне забезпечення
dc.subject.udc004.023
dc.titleСпосіб та програмне забезпечення для оптимізації маршрутів комівояжера
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Makhovoi_magistr.pdf
Розмір:
4.58 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ПЗКС)
Магістерські роботи