# Tractable Pathfinding for the Stochastic On-Time Arrival Problem

arXiv: https://arxiv.org/abs/1408.4490 · HTML: https://mlsanity.com/paper/1408.4490/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2014.

## Built on by (most cited first, 1 of 1)

- [Learning Graph-Indexed Trajectory Patterns for Stochastic On-Time Arrival Routing](https://mlsanity.com/paper/2508.17218/) (2025)

## Abstract (arXiv)

We present a new and more efficient technique for computing the route that maximizes the probability of on-time arrival in stochastic networks, also known as the path-based stochastic on-time arrival (SOTA) problem. Our primary contribution is a pathfinding algorithm that uses the solution to the policy-based SOTA problem---which is of pseudo-polynomial-time complexity in the time budget of the journey---as a search heuristic for the optimal path. In particular, we show that this heuristic can be exceptionally efficient in practice, effectively making it possible to solve the path-based SOTA problem as quickly as the policy-based SOTA problem. Our secondary contribution is the extension of policy-based preprocessing to path-based preprocessing for the SOTA problem. In the process, we also introduce Arc-Potentials, a more efficient generalization of Stochastic Arc-Flags that can be used for both policy- and path-based SOTA. After developing the pathfinding and preprocessing algorithms, we evaluate their performance on two different real-world networks. To the best of our knowledge, these techniques provide the most efficient computation strategy for the path-based SOTA problem for general probability distributions, both with and without preprocessing.