Stochastic On-time Arrival Problem with Levy Stable Distributions

This paper addresses the reliable shortest path problem with the following optimality criterion: maximizing the probability of arriving on time at a destination within a given time budget. As a link travel time distribution, we propose to use stable Levy distributions. The use of stable distributions allows replacing the computationally complex convolutions calculations with recalculating the Levy distribution parameters, which significantly reduces the running time of the algorithm. An experimental analysis of the algorithm conducted on a large-scale road network in Samara, Russia allow us to conclude that the proposed algorithm can significantly reduce the computation time with a slight increase in the path travel time.