Наблюдатель изменений в лесах кратчайших путей на динамических графах транспортных сетей

Цель работы – разработка базовых структур данных и эффективных по быстродействию и памяти алгоритмов слежения за изменениями предопределенных решений о множествах кратчайших путей на транспортных сетях, уведомления о которых получают автономные координируемые транспортные агенты с централизованным или коллективным управлением. Характерная особенность транспортных операций – независимость и асинхронность появления возмущений оптимальных решений, а также отсутствие глобального влияния отдельных возмущений на множество всех процессов на сети. Тем самым, очевидно, определяется целесообразность реализации идеи реоптимизации существующих решений в реальном времени по мере поступления информации о возмущениях структуры и параметров транспортной сети, различных ограничений на использование существующих кратчайших путей. В отличие от классических задач поиска кратчайших путей на статических или динамических графах, набор контролируемых наблюдателем ситуаций предлагается дополнить учетом ассоциаций деревьев кратчайших путей с фактически использующими такие пути агентами. Это позволит улучшить реактивность процессов уведомления агентов для своевременного переключения на новый путь. Пространство состояний поиска – динамически формируемый двудольный разреженный граф транспортной сети, представленный списком дуг. Базовый алгоритм поиска кратчайших путей использует схему Дейкстры, но реализует для формирования результата поиска метод бутстрэппинга. Компактность представления наблюдаемого леса кратчайших путей достигается отображением отдельных деревьев такого леса на проекцию вершин дерева в памяти, где позиция каждой вершины соответствует расстоянию от корня дерева. Предложенная версия построения процедуры поиска опирается на существующие в системах управления базами данных механизмы создания разных реляционных представлений физической модели данных. Это избавляет от необходимости решения технологических задач комплексирования гетерогенных моделей динамических транспортных сетей, распределения памяти. В результате спецификация различных правил логистики транспортных операций упрощается, так как такие операции в терминах объектно-ориентированных моделей легко определяются полиморфными классами переходов между узлами транспортной сети.

1. Sun Y., Yu X., Bie R., Song H. Discovering time-dependent shortest path on traffic graph for drivers towards green driving. Journal of Network and Computer Applications. 2017;83:204-212.

2. Рубанов И.В., Баркетов М.С., Ковалев М.Я. Моделирование движения объектов без остановок по сети пересекающихся маршрутов. Информатика. 2018;15(1):21-33.

3. Рыбак В.А., Рябычина О.П. Система экологического мониторинга атмосферного воздуха. Доклады БГУИР. 2020;18(4):36-43.

4. Ferone D., Festa P., Napoletano A., Pastore T. Shortest paths on dynamic graphs: a survey. Pesquisa Operacional. 2017;37(3):487-508.

5. Pugliese L.D.P., Guerriero F. A survey of resource constrained shortest path problems: Exact solution approaches. Networks. 2013;62(3):183-200.

6. Pallottino M.S., Scutelli M.G. A new algorithm for reoptimizing shortest paths when the arc costs change. Operations Research Letters. 2003;31(2):149-160.

7. Hooks E., Yang B. Updating paths in time-varying networks given arc weight changes. Transportation Science. 2005;39(4):451-464.

8. Nicholson T.A.J. Finding the Shortest Route between Two Points in a Network. The Computer Journal. 1966;9(3):275-280.

9. Ревотюк М.П., Кароли М.К., Хаджинова Н.В. Быстрый поиск кратчайших путей на графах с предопределенными решениями. Доклады БГУИР. 2014;4(82):73-79.