Stochastic on-time arrival problem in transit networks
Document Type
Journal Article
Publication Date
2019
Subject Area
place - north america, mode - bus, planning - methods
Keywords
Stochastic routing, Dynamic programming, Optimal policy, Dominance condition
Abstract
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.
Rights
Permission to publish the abstract has been given by Elsevier, copyright remains with them.
Recommended Citation
Liu, Y., Blandin, S., & Samaranayake, S. (2019). Stochastic on-time arrival problem in transit networks. Transportation Research Part B: Methodological, Vol 119, pp. 122-138.
Comments
Transportation Research Part B Home Page:
http://www.sciencedirect.com/science/journal/01912615