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

Постачальник даних: УкрІНТЕІ (Український Інститут науково-технічної експертизи та Інформації)

  Завантажити автореферат