Open AccessMethod for Reliable Shortest Path Determination in Stochastic Networks using Parametrically Defined Stable Probability Distributions
Author(s) -
Anton Agafonov,
Vladislav Myasnikov
Publication year - 2019
Publication title -
trudy spiiran
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 9
eISSN - 2078-9599
pISSN - 2078-9181
DOI - 10.15622/sp.2019.18.3.557-581
Subject(s) - shortest path problem , computer science , routing (electronic design automation) , mathematical optimization , path (computing) , reliability (semiconductor) , flow network , probability distribution , variance (accounting) , mathematics , statistics , computer network , theoretical computer science , graph , power (physics) , physics , accounting , quantum mechanics , business
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.