IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v30y2018i3p539-553.html
   My bibliography  Save this article

Risk Averse Shortest Paths: A Computational Study

Author

Listed:
  • Renaud Chicoisne

    (HEC Montréal, Montréal, Québec H3T 2A7, Canada)

  • Fernando Ordóñez

    (Universidad de Chile, Santiago, 8370456 Chile)

  • Daniel Espinoza

    (Gurobi Inc., Santiago, Chile)

Abstract

In this work we consider the shortest path problem with uncertainty in arc lengths and convex risk measure objective. We explore efficient implementations of sample average approximation (SAA) methods to solve shortest path problems when the conditional value at risk and entropic risk measures are used and there is correlation present in the uncertain arc lengths. Our work explores the use of different decomposition techniques to achieve an efficient implementation of SAA methods for these nonlinear convex integer optimization problems. A computational study shows the effect of geometry, uncertainty correlation and variance, and risk measure parameters on efficiency and accuracy of the methods developed.

Suggested Citation

  • Renaud Chicoisne & Fernando Ordóñez & Daniel Espinoza, 2018. "Risk Averse Shortest Paths: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 539-553, August.
    • Handle: RePEc:inm:orijoc:v:30:y:2018:i:3:p:539-553
    DOI: 10.1287/ijoc.2017.0795
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2017.0795
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2017.0795?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yingying Kang & Rajan Batta & Changhyun Kwon, 2014. "Value-at-Risk model for hazardous material transportation," Annals of Operations Research, Springer, vol. 222(1), pages 361-387, November.
    2. M. Avriel & A. C. Williams, 1970. "The Value of Information and Stochastic Programming," Operations Research, INFORMS, vol. 18(5), pages 947-954, October.
    3. Yaari, Menahem E, 1987. "The Dual Theory of Choice under Risk," Econometrica, Econometric Society, vol. 55(1), pages 95-115, January.
    4. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    5. Acerbi, Carlo & Tasche, Dirk, 2002. "On the coherence of expected shortfall," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1487-1503, July.
    6. Shipra Agrawal & Yichuan Ding & Amin Saberi & Yinyu Ye, 2012. "Price of Correlations in Stochastic Optimization," Operations Research, INFORMS, vol. 60(1), pages 150-162, February.
    7. Alexander, S. & Coleman, T.F. & Li, Y., 2006. "Minimizing CVaR and VaR for a portfolio of derivatives," Journal of Banking & Finance, Elsevier, vol. 30(2), pages 583-605, February.
    8. Alexandra Künzi-Bay & János Mayer, 2006. "Computational aspects of minimizing conditional value-at-risk," Computational Management Science, Springer, vol. 3(1), pages 3-27, January.
    9. Yongjia Song & Siqian Shen, 2016. "Risk-Averse Shortest Path Interdiction," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 527-539, August.
    10. Daniel Espinoza & Eduardo Moreno, 2014. "A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs," Computational Optimization and Applications, Springer, vol. 59(3), pages 617-638, December.
    11. Westgate, Bradford S. & Woodard, Dawn B. & Matteson, David S. & Henderson, Shane G., 2016. "Large-network travel time distribution estimation for ambulances," European Journal of Operational Research, Elsevier, vol. 252(1), pages 322-333.
    12. Yaari, Menahem E., 1969. "Some remarks on measures of risk aversion and on their uses," Journal of Economic Theory, Elsevier, vol. 1(3), pages 315-329, October.
    13. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    14. Hans Föllmer & Alexander Schied, 2002. "Convex measures of risk and trading constraints," Finance and Stochastics, Springer, vol. 6(4), pages 429-447.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.
    2. Utsav Sadana & Erick Delage, 2023. "The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 216-232, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Daniel Espinoza & Eduardo Moreno, 2014. "A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs," Computational Optimization and Applications, Springer, vol. 59(3), pages 617-638, December.
    2. Pengyu Qian & Zizhuo Wang & Zaiwen Wen, 2015. "A Composite Risk Measure Framework for Decision Making under Uncertainty," Papers 1501.01126, arXiv.org.
    3. Wang, Fan & Zhang, Chao & Zhang, Hui & Xu, Liang, 2021. "Short-term physician rescheduling model with feature-driven demand for mental disorders outpatients," Omega, Elsevier, vol. 105(C).
    4. Ruodu Wang & Ričardas Zitikis, 2021. "An Axiomatic Foundation for the Expected Shortfall," Management Science, INFORMS, vol. 67(3), pages 1413-1429, March.
    5. Steven Kou & Xianhua Peng & Chris C. Heyde, 2013. "External Risk Measures and Basel Accords," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 393-417, August.
    6. Yu, Jinping & Yang, Xiaofeng & Li, Shenghong, 2009. "Portfolio optimization with CVaR under VG process," Research in International Business and Finance, Elsevier, vol. 23(1), pages 107-116, January.
    7. Volker Kratschmer & Alexander Schied & Henryk Zahle, 2012. "Comparative and qualitative robustness for law-invariant risk measures," Papers 1204.2458, arXiv.org, revised Jan 2014.
    8. Ahmadi-Javid, Amir & Fallah-Tafti, Malihe, 2019. "Portfolio optimization with entropic value-at-risk," European Journal of Operational Research, Elsevier, vol. 279(1), pages 225-241.
    9. Balbás, Alejandro & Balbás, Beatriz & Balbás, Raquel, 2010. "CAPM and APT-like models with risk measures," Journal of Banking & Finance, Elsevier, vol. 34(6), pages 1166-1174, June.
    10. Amir Ahmadi-Javid & Malihe Fallah-Tafti, 2017. "Portfolio Optimization with Entropic Value-at-Risk," Papers 1708.05713, arXiv.org.
    11. Brandtner, Mario & Kürsten, Wolfgang, 2014. "Decision making with Conditional Value-at-Risk and spectral risk measures: The problem of comparative risk aversion," VfS Annual Conference 2014 (Hamburg): Evidence-based Economic Policy 100615, Verein für Socialpolitik / German Economic Association.
    12. Pospisil, Libor & Vecer, Jan & Xu, Mingxin, 2007. "Tradable measure of risk," MPRA Paper 5059, University Library of Munich, Germany.
    13. Volker Krätschmer & Alexander Schied & Henryk Zähle, 2014. "Comparative and qualitative robustness for law-invariant risk measures," Finance and Stochastics, Springer, vol. 18(2), pages 271-295, April.
    14. Shuo Gong & Yijun Hu & Linxiao Wei, 2022. "Distortion risk measures in random environments: construction and axiomatic characterization," Papers 2211.00520, arXiv.org, revised Mar 2023.
    15. Uhan, Nelson A., 2015. "Stochastic linear programming games with concave preferences," European Journal of Operational Research, Elsevier, vol. 243(2), pages 637-646.
    16. Mario Brandtner, 2016. "Spektrale Risikomaße: Konzeption, betriebswirtschaftliche Anwendungen und Fallstricke," Management Review Quarterly, Springer, vol. 66(2), pages 75-115, April.
    17. Brandtner, Mario, 2013. "Conditional Value-at-Risk, spectral risk measures and (non-)diversification in portfolio selection problems – A comparison with mean–variance analysis," Journal of Banking & Finance, Elsevier, vol. 37(12), pages 5526-5537.
    18. Brandtner, Mario & Kürsten, Wolfgang, 2015. "Decision making with Expected Shortfall and spectral risk measures: The problem of comparative risk aversion," Journal of Banking & Finance, Elsevier, vol. 58(C), pages 268-280.
    19. Samuel Solgon Santos & Marcelo Brutti Righi & Eduardo de Oliveira Horta, 2022. "The limitations of comonotonic additive risk measures: a literature review," Papers 2212.13864, arXiv.org, revised Jan 2024.
    20. Roman, Diana & Mitra, Gautam & Zverovich, Victor, 2013. "Enhanced indexation based on second-order stochastic dominance," European Journal of Operational Research, Elsevier, vol. 228(1), pages 273-281.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:30:y:2018:i:3:p:539-553. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.