Reliable Path Planning for Bus Networks Considering Travel Time Uncertainty

This paper investigates the problem of finding a priori shortest paths to guarantee a given probability of arriving on-time in a bus network under travel time uncertainty. This problem is especially important to residents who travel with public transportation systems, since their departure/routing choices are less flexible than those of private car drivers. In this paper, we propose a two-step polynomial-time algorithm to solve this problem. In the first step, we find all the valid paths between any an OD pair and store them for this OD pair before customers' query. In the second step, we apply a modified multi-criteria label-setting algorithm to quickly determine the reliable shortest paths from the stored paths. The influence of walking transfers and waiting time at bus stops are also considered. To prove that the Path-Storing strategy can be used in practice, we show that the complexity of the planning problem for bus networks is related with the degree distribution of the bus networks and is of polynomial time. The average number of valid paths between any two nodes is sufficiently small to store in advance. To test this trading-space-for-time strategy, we collect empirical data of Beijing bus network to characterize the uncertainties of bus arrival times and link travel times. Comparisons demonstrate that applying the Path-Storing Strategy significantly reduces path searching time.