Програмне забезпечення для вирішення задачі оптимізації транспортного руху
Вантажиться...
Дата
2024
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Розмір пояснювальної записки – 123 аркушів, містить 44 ілюстрацій, 22 таблиці, 3 додатків, 51 посилань на джерела.
Актуальність теми. Сучасні системи керування транспортними маршрутами потребують розроблення програмного забезпечення, що реалізує більш точні та швидкі алгоритми розв’язання задачі комівояжера, які забезпечують для великої кількості точок пошук найкращого маршруту з порівняно невеликою похибкою за коротший час. Основними недоліками існуючих реалізацій є стохастичність, обмежена адаптивність до параметрів задачі та велика чутливість до початкових умов, що призводить до невірних рішень та непотрібних витрат ресурсів. Через це, розроблення нового алгоритму для вирішення задачі оптимізації транспортного руху, який усуне ці недоліки, є актуальним завданням.
Мета дослідження. Основна мета полягає у покращенні процесу побудови транспортних маршрутів за рахунок розроблення програмного забезпечення, що реалізує новий алгоритм вирішення задачі комівояжера, який дозволяє знайти оптимальний або наближений до оптимального маршрут та сприяє покращенню транспортного руху.
Об'єкт дослідження: програмне забезпечення побудови оптимальних транспортних маршрутів для використання у різних предметних галузях.
Предмет дослідження: методи, підходи та алгоритми вирішення задачі комівояжера в основі прикладного програмного забезпечення побудови наближених до оптимальних маршрутів.
Для досягнення мети повинні бути виконані такі завдання:
– проаналізувати існуючі рішення та літературу;
– розробити новий алгоритм для розв’язання задачі комівояжера, враховуючи різні вхідні дані та умови;
– провести аналіз продуктивності розробленого алгоритму, порівнявши його результати з існуючими методами розв'язання задачі комівояжера та можливі шляхи його покращення;
– розробити програмне забезпечення побудови оптимальних транспортних маршрутів на основі запропонованого алгоритму;
– провести експерименти на різноманітних наборах даних, включаючи реальні сценарії, з метою оцінки роботи програмного забезпечення.
Науковою новизною роботи є реалізація інтерфейсу та необхідної функціональності при побудові наближених до оптимальних маршрутів з урахуванням особливостей запропонованого алгоритму розв’язання задачі комівояжера, що відрізняється від існуючих використанням тільки суттєвих вхідних даних і умов та дозволяє покращити пошук маршруту у різних варіантах застосування.
Практичне значення отриманих результатів полягає у тому, що запропоновано реалізацію, яка вирішить конкретні проблеми транспортної індустрії та надасть додаткові можливості для суспільства та транспортної інфраструктури.
Зв'язок з науковими програмами, планами, темами. Робота виконувалась на кафедрі інформатики та програмної інженерії Національного технічного університету України "Київський політехнічний інститут імені Ігоря Сікорського".
Апробація. Наукові положення дисертації пройшли апробацію на V Міжнародній науково-практичній конференції молодих вчених та студентів «Інженерія програмного забезпечення і передові інформаційні технології SoftTech-2023».
Публікації. Наукові положення дисертації опубліковані в:
1) Розробка програмного забезпечення на основі покращеного геометричного алгоритму для вирішення задачі оптимізації транспортного руху / В.В. Жнакін, Е. В. Жаріков // Матеріали V Міжнародної науково-практичної конференції молодих вчених та студентів «Інженерія програмного забезпечення і передові інформаційні технології SoftTech-2023» – м. Київ: НТУУ «КПІ ім. Ігоря Сікорського», 12-21 грудня 2023 р.
Опис
Ключові слова
комбінаторна оптимізація, задача комівояжера, оптимальний маршрут, час виконання, точність, iOS, Swift, UIKit, MapKit, combinatorial optimization, traveler's problem, optimal route, execution time, accuracy
Бібліографічний опис
Жнакін, В. В. Програмне забезпечення для вирішення задачі оптимізації транспортного руху : магістерська дис. : 121 Інженерія програмного забезпечення / Жнакін Володимир Володимирович. - Київ, 2024. - 123 с.