Stochastic on-time arrival problem in transit networks

Document Type

Journal Article

Publication Date


Subject Area

place - north america, mode - bus, planning - methods


Stochastic routing, Dynamic programming, Optimal policy, Dominance condition


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.


Permission to publish the abstract has been given by Elsevier, copyright remains with them.


Transportation Research Part B Home Page: