Pruning Techniques for the Stochastic on-time Arrival Problem An Experimental Study

Abstract. Computing shortest paths is one of the most researched topics in algorithm engineering. Currently available algorithms compute shortest paths in mere fractions of a second on continental sized road networks. In the presence of unreliability, however, current algorithms fail to achieve results as impressive as for the static setting. In contrast to speed-up techniques for static route planning, current implementations for the stochastic on-time arrival problem require the computationally expensive step of solving convolution products. Running times can reach hours when considering large scale networks. We present a novel approach to reduce this immense computational effort of stochastic routing based on existing techniques for alternative routes. In an extensive experimental study, we show that the process of stochastic route planning can be speed-up immensely, without sacrificing much in terms of accuracy.