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

Abstract

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