Морозов А. В. Вдосконалення методів оптимізації кільцевих маршрутів на транспортній мережі

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