Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей

В диссертационной работе рассматриваются задачи оптимизации на графах больших размерностей, возникающие в транспортной логистике, не имеющие эффективных алгоритмов нахождения точного решения. Исследуемый класс задач является вариацией задач маршрутизации транспорта с временными окнами и дополнительными ограничениями. Целью работы является разработка моделей и алгоритмов для практического решения задач, содержащих до 10000 клиентов. Автором были поставлены следующие задачи: разработка моделей и на их основе приближенных алгоритмов для решения многокритериальной задачи о поиске кратчайших путей; разработка новых и ускорение существующих алгоритмов для решения задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями. В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов. Автором созданы и исследованы новые алгоритмы и методы: приближенный алгоритм решения бикритериальной задачи о поиске кратчайших путей, псевдополиномиальный алгоритм для решения задачи о поиске кратчайших путей на графах с произвольно заданным частичным порядком, алгоритм построения начального приближения, многофазный алгоритм для решения задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями, метод фиктивных клиентов. Улучшены существующие результаты: разработана структура данных для быстрого выполнения обменов сегментов маршрутов; ускорена процедура поиска оптимальных обменов сегментов маршрутов. Разработан программный комплекс PlanVidia для практического решения задач маршрутизации с временными окнами и дополнительными ограничениям.