Stochastic on-time arrival problem in transit networks
For passengers and transit planners, this work provides a practical method for real-time route planning under uncertainty, though it is incremental in its algorithmic improvements.
The paper tackles the stochastic on-time arrival problem in transit networks with stochastic travel and waiting times. It proposes a dynamic programming algorithm with a dominance technique that reduces computation time by up to 90% in experiments on synthetic and Chicago transit networks.
This article considers the stochastic on-time arrival problem in transit networks where both the travel time and the waiting time for transit services are stochastic. A specific challenge of this problem is the combinatorial solution space due to the unknown ordering of transit line arrivals. We propose a network structure appropriate to the online decision-making of a passenger, including boarding, waiting and transferring. In this framework, we design a dynamic programming algorithm that is pseudo-polynomial in the number of transit stations and travel time budget, and exponential in the number of transit lines at a station, which is a small number in practice. To reduce the search space, we propose a definition of transit line dominance, and techniques to identify dominance, which decrease the computation time by up to 90% in numerical experiments. Extensive numerical experiments are conducted on both a synthetic network and the Chicago transit network.