Reliable Routing Strategies on Urban Transportation Networks

The problem of finding the most reliable routing strategy on urban transportation networks refers to determining the time-adaptive routing policy that maximizes the probability of on-time arrival at a destination given an arrival time threshold. The problem is defined on a stochastic and time-dependent network that captures real-world transportation systems’ inherent uncertainty and dynamism. To solve this problem, we present a dynamic programming–based algorithm that benefits from a node-time pairs queue implementation. In addition to improving the computational running time in most cases, this implementation supports different queue disciplines, leading to different algorithmic approaches: label-correcting and label-setting methods. We prove the correctness of the algorithm and derive its worst case time complexity. We present computational experiments over real-world, large-scale transportation networks with up to $\sim 33,000$ nodes, showing that the algorithm is a viable alternative to existing state-of-the-art methods. It can be four times faster for relatively tight arrival time thresholds and is competitive for looser ones. We also present experiments assessing the different queue disciplines used within the algorithm, the gains of the node–time pairs queue implementation, and comparing optimal strategies obtained from reliability and travel time objectives.