Reliable Routing Strategies on Urban Transportation Networks

Daniel Yamín (), Andrés L. Medaglia () and Arun Prakash Akkinepally ()
Additional contact information
Daniel Yamín: Centro para la Optimización y Probabilidad Aplicada, Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia 111711
Andrés L. Medaglia: Centro para la Optimización y Probabilidad Aplicada, Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia 111711
Arun Prakash Akkinepally: Caliper Corporation, Newton, Massachusetts 02461

Transportation Science, 2024, vol. 58, issue 2, 377-393

Abstract: 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 ∼ 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.

Keywords: stochastic time-dependent networks; on-time arrival probability; most reliable routing policy; dynamic programming; label-correcting method; label-setting method; urban transportation networks (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0013 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:58:y:2024:i:2:p:377-393

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().