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

Аннотация

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

Abstract

An increase in the number of vehicles, especially in large cities, and inability of the existing road infrastructure to distribute transport flows, leads to a higher congestion level in transport networks. This problem makes the solution to navigational problems more and more important. Despite the popularity of these tasks, many existing commercial systems find a route in deterministic networks, not taking into account the time-dependent and stochastic properties of traffic flows, i.e. travel time of road links is considered as constant. This paper addresses the reliable routing problem in stochastic networks using actual information of the traffic flow parameters. We consider the following optimality criterion: maximization of the probability of arriving on time at a destination given a departure time and a time budget. The reliable shortest path takes into account the variance of the travel time of the road network segments, which makes it more applicable for solving routing problems in transport networks compared to standard shortest path search algorithms that take into account only the average travel time of network segments. To describe the travel time of the road network segments, it is proposed to use parametrically defined stable Levy probability distributions. The use of stable distributions allows replacing the operation of calculating convolution to determine the reliability of the path to recalculating the parameters of the distributions density, which significantly reduces the computational time of the algorithm. The proposed method gives a solution in the form of a decision, i.e. the route proposed in the solution is not fixed in advance, but adaptively changes depending on changes in the real state of the network. An experimental analysis of the algorithm carried out on a large-scale transport network of Samara, Russia, showed that the presented algorithm can significantly reduce the computational time of the reliable shortest path algorithm with a slight increase in travel time.