Shortest Path Network Problems with Stochastic Arc Weights
Document Type
Article
Publication Date
11-2021
Abstract
This paper presents an approach to shortest path minimization for graphs with random weights of arcs. To deal with uncertainty we use the following risk measures: Probability of Exceedance (POE), Buffered Probability of Exceedance (bPOE), Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR). Minimization problems with POE and VaR objectives result in mixed integer linear problems (MILP) with two types of binary variables. The first type models path, and the second type calculates POE and VaR functions. Formulations with bPOE and CVaR objectives have only the first type binary variables. The bPOE and CVaR minimization problems have a smaller number of binary variables and therefore can be solved faster than problems with POE or VaR objectives. The paper suggested a heuristic algorithm for minimizing bPOE by solving several CVaR minimization problems. Case study (posted at web) numerically compares optimization times with considered risk functions.
DOI
10.1007/s11590-021-01712-5
Source Publication
Optimization Letters
Recommended Citation
Jordan, J.D., Uryasev, S. Shortest path network problems with stochastic arc weights. Optim Lett 15, 2793–2812 (2021). https://doi.org/10.1007/s11590-021-01712-5
Comments
The "Link to Full Text" on this page loads the PDF of the article, open-access through the Springer Nature SharedIt content-sharing initiative.
Please attribute the work using the citation indicated below.