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

Тенденция к увеличению количества транспортных средств, особенно в крупных городах, а также неспособность существующей дорожно-транспортной инфраструктуры распределять транспортные потоки, ведут к чрезмерной загрузке транспортных сетей и образованию дорожных заторов. Нерешенность данных проблем подчеркивает актуальность навигационных задач нахождения кратчайшего пути или оптимального маршрута движения. Несмотря на популярность этих задач, многие существующие коммерческие системы строят маршрут движения в детерминированных сетях, не учитывая зависящие от времени и стохастические свойства транспортных потоков. В работе рассматривается задача нахождения надежного маршрута движения в стохастической транспортной сети, максимизирующего вероятность прибытия в пункт назначения в течение заданного интервала времени. Надежный кратчайший путь учитывает дисперсию времени прохождения сегментов дорожной сети, что делает его более применимым для решения задач маршрутизации в транспортных сетях по сравнению со стандартными алгоритмами поиска кратчайшего пути, учитывающими только среднее время прохождения дорожных сегментов. Для описания времени прохождения сегментов дорожной сети предлагается использовать параметрически заданные устойчивые распределения вероятностей Леви. Использование устойчивых распределений позволяет перейти от операции вычисления свертки для определения надежности пути к пересчету параметров плотности распределения, что значительно сокращает время исполнения алгоритма. В работе решается задача нахождения адаптивного маршрута движения. Адаптивность подразумевает зависимость выбора следующего используемого дорожного сегмента от времени прибытия в вершину графа и определяется реальным состоянием дорожной сети. Экспериментальный анализ алгоритма, проведенный на крупномасштабной транспортной сети города Самара, показал, что представленный алгоритм позволяет значительно сократить время решения задачи нахождения надежного маршрута движения при незначительном увеличении времени проезда.