Левченко А. Ю. Методи прискорювання обчислень в задачах оптимальної маршрутизації

Об'єкт дослідження - замкнені маршрути, що забезпечують доставку вантажів, пасажирів, інформаційних повідомлень і раціонально використовують можливості транспортних мереж. Мета дослідження - розробка та вдосконалення методів оптимізації замкнених маршрутів на транспортних мережах для підвищення ефективності процесів перевезень пасажирів та вантажів. Методи дослідження - результати теорії графів для знаходження лісу дерев, точок зчленування, мостів; методи побудови в графах найкоротших шляхів; елементи теорії паросполучень для розв'язку варіанту задачі про призначення, яку використано у якості релаксації у методі гілок та меж; методи розв'язання задач цілочисельної оптимізації для порівняльного аналізу з розробленими методами; елементи теорії складності алгоритмів для оцінки трудомісткості побудови замкнених маршрутів. Апаратура - персональний комп'ютер. Теоретичні і практичні результати досліджень - розроблені математичні моделі задач і методи їх розв'язання спрямовані на економічно обґрунтований пошук замкнутих маршрутів. Наукова новизна - вперше запропоновано точний метод розв'язання загальної задачі комівояжеру із ефективною процедурою її зведення до сукупності підзадач меншої розмірності; процедура стримує зріст часових витрат, який викликано збільшенням об'єму вхідних даних задачі; вперше розроблено наближений метод розв'язання загальної задачі комівояжеру із трудомісткістю, яка оцінюється поліномом третього ступеню від порядку вхідної матриці, та з відносною похибкою, представленою константою. Метод призначено для розв'язання у реальному масштабі часу задач маршрутизації з прийнятною точністю та високою швидкодією; отримав подальший розвиток метод гілок та меж для розв'язання класу задач комівояжера. Модифікація перевершує за швидкодією метод Літла за рахунок швидкого обчислення більш точної нижньої межі вартості шуканого маршруту, яка встановлюється в результаті розв'язку одного з варіантів задачі про призначення, а також за рахунок зберігання гранично обмеженого списку даних у вершинах дерева перебору. Результати дисертаційної роботи впроваджені в Новоград-Волинській райспоживспілці Житомирської області. Результати досліджень використовуються у навчальному процесі за напрямком "Програмна інженерія" при викладанні дисциплін "Комп'ютерна дискретна математика", "Математичні методи дослідження операцій", "Основи математичного програмування", в лабораторному практикумі, при курсовому та дипломному проектуванні. Наукові теоретичні та практичні результати дисертаційної роботи можуть бути використані: розроблене програмне забезпечення спроможне вирішувати прикладні задачі управління транспортними перевезеннями вантажів та пасажирів у реальних умовах.