  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.
