Shortest Path Network Problems with Stochastic Arc Weights

Document Type


Publication Date



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.


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.



Source Publication

Optimization Letters