Павленко А. І. Моделювання і оптимізація маршрутів у транспортних мережах

Дисертація присвячена моделюванню і оптимізації маршрутів у транспортних мережах, а саме розробці алгоритмів розв'язування та експериментального програмного комплексу для побудови оптимальних шляхів за критерієм вартості в залежних від часу мережах авіаперельотів з урахуванням обмежень користувача і необхідності виконання розрахунків у реальному часі. Сформульовано спеціальну задачу пошуку оптимального за критерієм вартості шляху мандрівника з користувацькими умовами: початковий і цільовий пункт подорожі, часове вікно, максимальна кількість транзитних пунктів і тривалість подорожі, бажані і заборонені проміжні пункти. Відмінність даної задачі від існуючих постановок полягає у врахуванні таких властивостей транспортної мережі, як залежність її характеристик від часу. Аналіз подання моделей різних транспортних мереж виявив їх відмінності і можливість застосування евристичних алгоритмів розв'язування поставленої задачі. Запропоновано алгоритм на основі міток і ряд алгоритмів на основі модифікації оптимізації мурашиними колоніями. Алгоритм міток показав задовільні результати для невеликих мереж, але значне зростання часу виконання у порівнянні з мурашиним алгоритмом з ростом мережі. Алгоритм мурашиних систем модифіковано з урахуванням специфіки задачі, а саме операції бектрекінгу, локального пошуку, табу-списків, добудови допустимого маршруту, відсікання простору пошуку методом гілок і меж. Для покращення точності обчислень для міжрегіональних маршрутів запропоновано диверсифікований алгоритм мурашиних систем. При пошуку кільцевих або міжрегіональних маршрутів пропонується застосовувати розроблений двонаправлений алгоритм систем мурашиних колоній (АСМК). Задоволення вимог адаптивності та роботи в реальному часі програмного комплексу досягається запропонованим алгоритмом з попередньою обробкою даних, який використовує АСМК для пошуку оптимальних шляхів для всіх пар вершин мережі, а потім використовує цю інформацію для побудови відносних оцінок якості кожного сполучення за критерієм вартості. Оцінки якості використовуються для пошуку маршруту в реальному часі. Така задача та методи її розв’язування актуальні для пошуку оптимальних маршрутів мандрівників в реальному часі в мережі громадського транспорту.