Маций О. Б. Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу

Об’єкт дослідження – замкнені маршрути в задачах транспортного типу. Мета роботи – розроблення та модифікація математичних методів знаходження оптимальних замкнених маршрутів у задачах транспортного типу. Методи дослідження – у дисертаційній роботі використано елементи теорії графів для побудови моделі маршрутизації та удосконалення методів розв’язання задачі про призначення, задачі знаходження 2-фактора мінімальної ваги і окремих випадків VRP (Vehicle Routing Problem), методи комбінаторної оптимізації для розроблення модифікації алгоритму Літтла, основи теорії складності для оцінювання трудомісткості розроблених методів. Практичні результати – розроблені моделі та методи оптимізації орієнтовані на вдосконалення організації перевезень у реальному масштабі часу і в реальних умовах руху транспортних засобів. Наукова новизна отриманих результатів полягає в наступному: вперше запропоновано рекурентний метод розв’язання задачі про призначення, що містить швидку за часовими параметрами процедуру побудови найкоротшого збільшуючого шляху в зваженому графі транспортної мережі, чим досягається перевага в швидкості обчислень перед іншими методами оптимізації замкнених маршрутів; вдосконалено рекурентний метод побудови зважених паросполучень, на основі якого будується 2-фактор мінімальної ваги з найменшою на теперішній час часовою складністю, в результаті зведення 2-фактора до обмеженої задачі про призначення; вперше запропоновано модифікацію алгоритму Літтла, орієнтованому на зменшення часу розв’язання задач транспортного типу, що містить для швидкого обчислення точніших оцінок меж шуканого оптимуму один з окремих випадків задачі знаходження 2-фактора мінімальної ваги. Основні результати дисертаційного дослідження отримано в межах виконання планових бюджетних досліджень в Харківському національному автомобільно-дорожньому університеті. Результати дисертаційної роботи використані в навчальному процесі на кафедрі комп’ютерних технологій і мехатроніки Харківського національного автомобільно-дорожнього університету при викладенні дисципліни «Системний аналіз» та «Математичні методи дослідження операцій». Також отримані результати упроваджені в розробках науково-виробничого підприємства «Карсис».