Skip to main content

Advertisement

Springer Nature Link
Log in

Shortest path network problems with stochastic arc weights

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)

    Article  MathSciNet  Google Scholar 

  2. Bellman, R.E.: On a routing problem. Q. Appl. Math 16, 87–90 (1958)

    Article  Google Scholar 

  3. Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)

    Book  Google Scholar 

  4. Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston (1976)

    MATH  Google Scholar 

  5. Floyd, R.W.: Algorithm 97 (shortest path). Commun. ACM 5(6), 345 (1962)

    Article  Google Scholar 

  6. Warshall, S.: A theorem on Boolean matrices. J. ACM 9(1), 11–12 (1962)

    Article  MathSciNet  Google Scholar 

  7. Moore, E.F.: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285–292. Harvard University Press (1959)

  8. Lee, C.Y.: An algorithm for path connection and its applications. IRE Trans. Electron. Comput. 10(3), 346–365 (1961)

    Article  MathSciNet  Google Scholar 

  9. Carlyle, W.M., Royset, J.O., Wood, R.K.: Lagrangean relaxation and enumeration for solving constrained shortest-path problems. Networks 52(4), 256–270 (2008)

    Article  MathSciNet  Google Scholar 

  10. Royset, J.O., Carlyle, W.M., Wood, R.K.: Routing military aircraft with a constrained shortest-path algorithm. Mil. Oper. Res. 14(3), 31–52 (2009)

    Article  Google Scholar 

  11. Royset, J.O., Wood, R.K.: Solving the bi-objective maximum-flow network-interdiction problem. INFORMS J. Comput. 19(2), 175–184 (2007)

    Article  MathSciNet  Google Scholar 

  12. Frank, H.: Shortest paths in probability graphs. Oper. Res. 17, 583–599 (1969)

    Article  Google Scholar 

  13. Mirchandani, B.P.: Shortest distance and reliability of probabilistic networks. Comput. Oper. Res. 3, 347–676 (1976)

    Article  Google Scholar 

  14. Murthy, I., Sarkar, S.: A relaxation-based pruning technique for a class of stochastic shortest path problems. Transp. Sci. 30(3), 220–236 (1996)

    Article  Google Scholar 

  15. Loui, P.: Optimal paths in graphs with stochastic or multidimensional weights. Commun. ACM 26, 670–676 (1983)

    Article  MathSciNet  Google Scholar 

  16. Xiaoyu, Ji.: Models and algorithm for stochastic shortest path problem. Appl. Math. Comput. 170(1), 503–514 (2005)

    MathSciNet  MATH  Google Scholar 

  17. Boginski, V.L., Commander, C.W., Turko, T.: Polynomial-time identification of robust network flows under uncertain arc failures. Optim. Lett. 3(3), 461–473 (2009)

    Article  MathSciNet  Google Scholar 

  18. Elci, O., Noyan, N., Bulbul, K.: Chance-constrained stochastic programming under variable reliability levels with an application to humanitarian relief network design. Comput. Oper. Res. 96, 91–107 (2018)

    Article  MathSciNet  Google Scholar 

  19. Yu, G., Yang, J.: On the robust shortest path problem. Comput. Oper. Res. 25, 457–468 (1998)

    Article  Google Scholar 

  20. Pessoa, A., Pugliese, L., Guerriero, F., Poss, M.: Robust constrained shortest path problems under budgeted uncertainty. Networks (2015). https://doi.org/10.1002/net.21615

    Article  MathSciNet  MATH  Google Scholar 

  21. Pascoal, M., Resende, M.: Reducing the minmax regret robust shortest path problem with finite multi-scenarios. In: Bourguignon, P., Jeltsch, R., Pinto, A., Viana, M. (eds.) CIM Series in Mathematical Sciences—Mathematics of Planet Earth: Energy and Climate Change (Dynamics, Games and Science), vol. 2. Springer (2014)

    Google Scholar 

  22. Pascoal, M., Resende, M.: Minmax regret robust shortest path problem in a finite multi-scenario model. Appl. Math. Comput. 241, 88–111 (2014)

    MathSciNet  MATH  Google Scholar 

  23. Murthy, I., Her, S.-S.: Solving min-max shortest path problems on a network. Naval Res. Log. 39, 669–683 (1992)

    Article  MathSciNet  Google Scholar 

  24. Montemanni, R., Gambardella, L., Donati, V.: A branch and bound algorithm for the robust shortest path problem with interval data. Oper. Res. Lett. 32, 225–232 (2004)

    Article  MathSciNet  Google Scholar 

  25. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. Ser. B 98, 49–71 (2003)

    Article  MathSciNet  Google Scholar 

  26. Bruni, M.E., Guerriero, F.: An enhanced exact procedure for the absolute robust shortest path problem. Int. Trans. Oper. Res. 17, 207–220 (2010)

    Article  MathSciNet  Google Scholar 

  27. Catanzaro, D., Labbé, M., Salazar-Neumann, M.: Reduction approaches for robust shortest path problems. Comput. Oper. Res. 38, 1610–1619 (2011)

    Article  MathSciNet  Google Scholar 

  28. Kasperski, A., Zieliński, P.: Robust discrete optimization under discrete and interval uncertainty: a survey. In: Doumpos, M., Zopounidis, C., Grigoroudis, E. (eds.) Robustness Analysis in Decision Aiding, Optimization, and Analytics. International Series in Operations Research & Management Science, vol. 241. Springer, Cham (2016)

    Google Scholar 

  29. Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21–41 (2000)

    Article  Google Scholar 

  30. Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26(7), 1443–1471 (2002)

    Article  Google Scholar 

  31. Mafusalov, A., Uryasev, S.: Buffered probability of exceedance: mathematical properties and optimization algorithms. SIAM J. Optim. 28(2), 1077–1103 (2018)

    Article  MathSciNet  Google Scholar 

  32. Optimization and Risk Management: Case Studies with Portfolio Safeguard (PSG). AORDA (2010). ISBN: 0982821301

  33. Rockafellar, R.T., Royset, J.O.: On buffered failure probability in design and optimization of structures. J. Reliab. Eng. Syst. Saf. 99, 499–510 (2010)

    Article  Google Scholar 

  34. Rockafellar, R.T., Uryasev, S.: The fundamental risk quadrangle in risk management, optimization and statistical estimation. Surv. Oper. Res. Manag. Sci. 18, 33–53 (2013)

    MathSciNet  Google Scholar 

  35. Davis, J.R., Uryasev, S.: Analysis of tropical storm damage using buffered probability of exceedance. Nat. Hazards 83, 465–483 (2016)

    Article  Google Scholar 

  36. Kulkarni, V.G.: Shortest paths in networks with exponentially distributed arc lengths. Networks 16, 255–274 (1986)

    Article  MathSciNet  Google Scholar 

  37. Davis, R., Prieditis, A.: The expected length of a shortest path. Inf. Process. Lett. 46, 135–141 (1993)

    Article  MathSciNet  Google Scholar 

  38. Pavlikov, K., Veremyev, A., Pasiliao, E.L.: Optimization of value-at-risk: computational aspects of MIP formulations. J. Oper. Res. Soc. 69, 676–690 (2017). https://doi.org/10.1057/s41274-017-0197-4

    Article  Google Scholar 

  39. Norton, M., Mafusalov, A., Uryasev, S.: Cardinality of upper average and its application to network optimization. SIAM J. Optim. 28(2), 1726–1750 (2018)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Air Force Institute of Technology, Wright-Patterson AFB, USA

    Jeremy D. Jordan

  2. Stony Brook University, Stony Brook, USA

    Stan Uryasev

Authors
  1. Jeremy D. Jordan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stan Uryasev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremy D. Jordan.

Additional information

Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-021-01712-5

Keywords

Search

Navigation