Tractable Pathfinding for the Stochastic On-Time Arrival Problem

We present a new technique for fast computation of the route that maximizes the probabil-ity of on-time arrival in stochastic networks, also known as the path-based stochastic on-time arrival (SOTA) problem. We utilize the solution to the policy-based SOTA problem, which is of pseudopolynomial time complexity in the time budget of the journey, as a heuristic for efficiently computing the optimal path. We also introduce Arc-Potentials, an extension to the Arc-Flags pre-processing algorithm, which improves the efficiency of the graph pre-processing and reduces the computation time. Finally, we present extensive numerical results demonstrating the effec-tiveness of our algorithm and observe that its running time when given the policy (which can be efficiently obtained using pre-processing) is almost always linear in the length of the optimal path for our test networks