On the shortest $$\alpha$$ α -reliable path problem

David Corredor-Montenegro (), Nicolás Cabrera (), Raha Akhavan-Tabatabaei () and Andrés L. Medaglia ()
Additional contact information
David Corredor-Montenegro: Universidad de los Andes
Nicolás Cabrera: Universidad de los Andes
Raha Akhavan-Tabatabaei: Sabanci University
Andrés L. Medaglia: Universidad de los Andes

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2021, vol. 29, issue 1, No 13, 287-318

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

Keywords: Constrained shortest path problem; Pulse algorithm; Stochastic shortest path; Phase-type distributions; Spatial correlation; Chance constraints; 90-08; 90B15; 90B06; 90C35 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-021-00592-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:topjnl:v:29:y:2021:i:1:d:10.1007_s11750-021-00592-3

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-021-00592-3

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().