Logo image
Back
Shortest path problem with arc failure scenarios
Journal article   Open access   Peer reviewed

Shortest path problem with arc failure scenarios

Preethi Issac and Ann Melissa Campbell
EURO Journal on Transportation and Logistics, Vol.6(2), pp.139-163
06/01/2017
DOI: 10.1007/s13676-015-0092-6
url
https://doi.org/10.1007/s13676-015-0092-6View
Published (Version of record) Open Access

Abstract

We consider a shortest path problem from source to destination over a set of arc failure scenarios, considering the probability of different scenarios. A primary path is chosen, which is the first path a driver will take, along with a set of alternative paths to use when an impassible road is encountered. These paths should minimize the expected cost to reach the destination and be useful in natural disaster applications. Our paper includes a formal problem description and integer programming model for this new problem. We also provide an exact algorithm based on the modified label-correcting algorithm but with extended labels that preserve information about the scenarios. We describe dominance rules and how to use a version of the A-star algorithm to generate an initial bound. We conduct computational experiments with real road data sets with varying number of scenarios and disaster intensities. These experiments show the value of the dominance rules and initial bounds, as well as the structure of the chosen paths.
 Business and Management Logistics Management Science Operations Research Operations Research/Decision Theory Optimization Research Paper

Details

Metrics

27 Record Views
6 Times Cited - Web of Science
Logo image