УДОСКОНАЛЕНИЙ ГЕОМЕТРИЧНИЙ АЛГОРИТМ ТА ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ В ЗАДАЧАХ ОПТИМІЗАЦІЇ ТРАНСПОРТНИХ МАРШРУТІВ

Анотація

Сучасні системи керування транспортними маршрутами потребують розроблення програмного забезпечення, що реалізує більш точні та швидкі алгоритми розв’язання задачі комівояжера, які забезпечують для великої кількості точок пошук найкращого маршруту з порівняно невеликою похибкою за коротший час. Основними недоліками існуючих реалізацій є стохастичність, обмежена адаптивність до параметрів задачі та велика чутливість до початкових умов, що призводить до невірних рішень та непотрібних витрат ресурсів. У статті наведена постановка задачі пошуку найменшого можливого циклічного маршруту, що проходить через заданий набір міст, починаючи і закінчуючи в тому самому місті. У результаті, алгоритм повинен знайти послідовність відвідування міст, щоб загальна довжина шляху між ними була мінімальною, і шлях проходив через кожне місто рівно один раз. Проведено експериментальні дослідження та порівняно ефективність удосконаленого геометричного алгоритму для 10, 50, 100 та 1000 міст. Результати роботи удосконаленого геометричного алгоритму для 10 міст порівняно з базовим геометричним алгоритмом та алгоритмом повного перебору, щоб переконатися, що є покращення не тільки часу пошуку маршруту, але й довжини знайденого шляху. Для 50, 100 1000 міст результати роботи удосконаленого геометричного алгоритму порівняємо з базовим геометричним алгоритмом, генетичним алгоритмом і алгоритмом оптимізації мурашиної колонії, щоб переконатися, що удосконалений геометричний алгоритм працює не гірше і швидше ніж інші алгоритми. У випадках, коли удосконалений геометричний алгоритм працює з похибкою відносно інших алгоритмів, він дозволяє отримати суттєвий виграш за часом виконання. Експерименти показали, що запропонований у роботі удосконалений геометричний алгоритм дозволяє детерміновано знаходити найкращий маршрут з похибкою 6,82% для 1000 міст. При цьому він знаходить рішення у 2,8 рази швидше, ніж алгоритм мурашиних колоній, та у 265 раз швидше, ніж генетичний алгоритм. Наведено приклад реалізації удосконаленого геометричного алгоритму мовою програмування swift для використання на платформи iOS.