Розробка програмного забезпечення на основі покращеного геометричного алгоритму для вирішення задачі оптимізації транспортного руху
Вантажиться...
Дата
2023
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Сучасні системи керування транспортними засобами логістичних компаній потребують розробки програмного забезпечення, здатного прораховувати найкоротші відстані з невеликою похибкою і за відносно короткий час, який враховуватиме те, що ці місця з'єднуються не прямою лінією, а складнішою фігурою. Основним недоліком більшості існуючих реалізацій є те, що вони не аналізують існуючі дороги між місцями, а обчислюють лише найкоротші відстані по координатах, що призводить до неточних рішень, які неможливо застосувати у реальному світі. У цій роботі наведена постановка завдання пошуку найменшого можливого циклічного маршруту, який проходить через заданий набір міст, починаючи і закінчуючи в тому самому місті. У результаті, алгоритм повинен знайти послідовність відвідування міст, щоб загальна довжина шляху між ними була мінімальною, і шлях проходив через кожне місто рівно один раз. Проведено експериментальні дослідження з існуючими дорогами для 10. Результати для 10 міст порівняні з алгоритмом повного перебору, який також аналізує дороги. Наведено приклад реалізації покращеного геометричного алгоритму з використанням існуючих доріг мовою програмування swift для використання на платформі iOS.
Опис
Ключові слова
задача комівояжера, оптимальний шлях, комбінаторна оптимізація, MAPKIT, iOS traveling salesman problem, optimal way, combinatory optimization
Бібліографічний опис
Жнакін, В. В. Розробка програмного забезпечення на основі покращеного геометричного алгоритму для вирішення задачі оптимізації транспортного руху / Жнакін Володимир Володимирович // Інженерія програмного забезпечення і передові інформаційні технології (SoftTech-2023) : матеріали V Міжнародної науково-практичної конференції молодих вчених та студентів, присвячених 125-й річниці КПІ ім. Ігоря Сікорського (19-21 грудня 2023 р., Київ). – Київ : КПІ ім. Ігоря Сікорського, ІПІ ФІОТ, 2023. – С. 128-131. – Бібліогр.: 4 назв.