Reliable Shortest Path Problems in Stochastic Time-Dependent Networks |
| |
| Authors: | Bi Yu Chen William H K Lam Agachai Sumalee Qingquan Li Mei Lam Tam |
| |
| Institution: | 1. State Key Laboratory of Information Engineering in Surveying, Mapping, and Remote Sensing, Wuhan University, Wuhan, China;2. Department of Civil and Environmental Engineering, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;3. Department of Civil and Environmental Engineering, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| |
| Abstract: | This study investigates the time-dependent reliable shortest path problem (TD-RSPP), which is commonly encountered in congested urban road networks. Two variants of TD-RSPP are considered in this study. The first variant is to determine the earliest arrival time and associated reliable shortest path for a given departure time, referred to as the “forward” TD-RSPP. The second problem is to determine the latest departure time and associated reliable shortest path for a given preferred arrival time, referred as the “backward” TD-RSPP. It is shown in this article that TD-RSPP is not reversible. The backward TD-RSPP cannot be solved by the algorithms designed for the forward problem using the reverse search from destination to origin. In this study, two efficient solution algorithms are proposed to solve the forward and backward TD-RSPP exactly and the optimality of proposed algorithms is rigorously proved. The proposed solution algorithms have potential applications in both advanced traveler information systems and stochastic dynamic traffic assignment models. |
| |
| Keywords: | Dynamic Traffic Assignment Models Reliable Shortest Path Problem Stochastic Time-Dependent Network Travel Time Reliability |
|
|
