An online shortest path algorithm for reliable routing in schedule-based transit networks considering transfer failure probability


Alireza Khani

Document Type

Journal Article

Publication Date


Subject Area

operations - reliability, operations - scheduling, ridership - behaviour, technology - intelligent transport systems, planning - methods


Schedule-based transit assignment, Stochastic shortest path, Transfer reliability, Online shortest path, Real-time arrival information


Most schedule-based transit assignment models assume deterministic vehicle arrival/departure times, in contrast to random vehicle arrival assumption in frequency-based models. This assumption simplifies user route choice behavior and fails to capture users’ response to unreliable service. Moreover, the inherent inconvenience of transfers, primarily due to uncertain waiting time and failure probability, has always been a challenge in modeling transit networks, to the extent that determining an appropriate transfer penalty for heterogeneous user population is still a question when using planning models. This study aims to bridge the gap between frequency-based and schedule-based transit assignment models, and proposes a path algorithm in schedule-based transit networks with stochastic vehicle arrival times to model users’ adaptive behavior in response to unreliable service. Path reliability is modeled by link failure probability, and an online shortest path algorithm is developed to find a routing policy with minimum expected travel time given preferred arrival time to destination. Complexity analyses and computational tests indicate that the model has potential for application in large-scale transit networks. Numerical tests verify that the model assigns passengers to more reliable paths with lower transfer rate without a need for a large transfer penalty.


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


Transportation Research Part B Home Page: