Corredor-Montenegro, David and Cabrera, Nicolas and Akhavan, Raha and Medaglia, Andres L.
(2021)
*On the shortest alpha-reliable path problem.*
Top (SI), 29
(1).
pp. 287-318.
ISSN 1134-5764 (Print) 1863-8279 (Online)

PDF

26.pdf

Download (3MB)

26.pdf

Download (3MB)

Official URL: http://dx.doi.org/10.1007/s11750-021-00592-3

## 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 short- est 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 experi- ments 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.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | constrained shortest path problem, pulse algorithm, stochastic shortest path, phase-type distributions, spatial correlation, chance constraints |

Subjects: | Q Science > QA Mathematics > QA273-280 Probabilities. Mathematical statistics |

Divisions: | Sabancı Business School Sabancı Business School > Operations Management and Information Systems |

Depositing User: | Raha Akhavan |

Date Deposited: | 22 Aug 2021 17:04 |

Last Modified: | 17 Aug 2022 16:15 |

URI: | https://research.sabanciuniv.edu/id/eprint/41739 |