On the shortest α-reliable path problem

• David Corredor-Montenegro ^[1] ; Nicolás Cabrera ^[1] ; Raha Akhavan-Tabatabaei ^[2] ; Andrés L. Medaglia ^[1]
  1. [1] Universidad de Los Andes

     Universidad de Los Andes

     Colombia

     
  2. [2] Sabancı University

     Sabancı University

     Turquía

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 29, Nº. 1, 2021, págs. 287-318
• Idioma: inglés
• DOI: 10.1007/s11750-021-00592-3
• Enlaces
  • Texto completo
• Resumen

  • In this variant of the constrained shortest path problem, the time of traversing an arc is given by a non-negative continuous random variable. The problem is to find a minimum cost path from an origin to a destination, ensuring that the probability of reaching the destination within a time limit meets a certain reliability threshold. To solve this problem, we extend the pulse algorithm, a solution framework for shortest path problems with side constraints. To allow arbitrary non-negative continuous travel-time distributions, we model the random variables of the travel times using Phase-type distributions and Monte Carlo simulation. We conducted a set of experiments over small- and medium-size stochastic transportation networks with and without spatially-correlated travel times. As an alternative to handling correlations, we present a scenario-based approach in which the distributions of the arc travel times are conditioned to a given scenario (e.g., variable weather conditions). Our methodology and experiments highlight the relevance of considering on-time arrival probabilities and correlations when solving shortest path problems over stochastic transportation networks.