Реєстраційний номер
0419U002155, Кандидатська дисертація
На здобуття
Кандидат технічних наук
Дата захисту
12-04-2019
Статус
Захищена
Назва роботи
Моделювання і оптимізація маршрутів у транспортних мережах
Здобувач
Павленко Анна Ігорівна,
Керівник Гуляницький Леонід Федорович
Опонент Томашевський Валентин Миколайович
Опонент Снитюк Віталій Євгенович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Інститут кібернетики імені В.М. Глушкова НАН України
Опис
Дисертація присвячена моделюванню і оптимізації маршрутів у транспортних мережах, а саме розробці алгоритмів розв'язування та експериментального
програмного комплексу для побудови оптимальних шляхів за критерієм вартості в залежних від часу мережах авіаперельотів з урахуванням обмежень користувача і необхідності виконання розрахунків у реальному часі.
Сформульовано спеціальну задачу пошуку оптимального за критерієм вартості шляху мандрівника з користувацькими умовами: початковий і цільовий
пункт подорожі, часове вікно, максимальна кількість транзитних пунктів і тривалість подорожі, бажані і заборонені проміжні пункти. Відмінність даної задачі
від існуючих постановок полягає у врахуванні таких властивостей транспортної мережі, як залежність її характеристик від часу. Аналіз подання моделей різних
транспортних мереж виявив їх відмінності і можливість застосування евристичних алгоритмів розв'язування поставленої задачі.
Запропоновано алгоритм на основі міток і ряд алгоритмів на основі модифікації оптимізації мурашиними колоніями. Алгоритм міток показав задовільні результати для невеликих мереж, але значне зростання часу виконання у порівнянні з мурашиним алгоритмом з ростом мережі. Алгоритм мурашиних систем
модифіковано з урахуванням специфіки задачі, а саме операції бектрекінгу, локального пошуку, табу-списків, добудови допустимого маршруту, відсікання
простору пошуку методом гілок і меж. Для покращення точності обчислень для міжрегіональних маршрутів запропоновано диверсифікований алгоритм
мурашиних систем. При пошуку кільцевих або міжрегіональних маршрутів пропонується застосовувати розроблений двонаправлений алгоритм систем
мурашиних колоній (АСМК).
Задоволення вимог адаптивності та роботи в реальному часі програмного комплексу досягається запропонованим алгоритмом з попередньою обробкою
даних, який використовує АСМК для пошуку оптимальних шляхів для всіх пар вершин мережі, а потім використовує цю інформацію для побудови відносних
оцінок якості кожного сполучення за критерієм вартості. Оцінки якості використовуються для пошуку маршруту в реальному часі. Така задача та методи її
розв’язування актуальні для пошуку оптимальних маршрутів мандрівників в реальному часі в мережі громадського транспорту.
Дата реєстрації
2019-04-18
Додано/оновлено в НРАТ
2020-04-03 / 2026-06-29
