IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v274y2019i2p671-686.html
   My bibliography  Save this article

Algorithms and uncertainty sets for data-driven robust shortest path problems

Author

Listed:
  • Chassein, André
  • Dokka, Trivikram
  • Goerigk, Marc

Abstract

We consider robust shortest path problems, where the aim is to find a path that optimizes the worst-case performance over an uncertainty set containing all relevant scenarios for arc costs. The usual approach for such problems is to assume this uncertainty set given by an expert who can advise on the shape and size of the set.

Suggested Citation

  • Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:2:p:671-686
    DOI: 10.1016/j.ejor.2018.10.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718308579
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.10.006?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    2. Chassein, André B. & Goerigk, Marc, 2015. "A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 739-747.
    3. Chassein, André & Goerigk, Marc, 2018. "Variable-sized uncertainty and inverse problems in robust optimization," European Journal of Operational Research, Elsevier, vol. 264(1), pages 17-28.
    4. Dimitris Bertsimas & David B. Brown, 2009. "Constructing Uncertainty Sets for Robust Linear Optimization," Operations Research, INFORMS, vol. 57(6), pages 1483-1495, December.
    5. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    6. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    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. Dimitrios Letsios & Jeremy T. Bradley & Suraj G & Ruth Misener & Natasha Page, 2021. "Approximate and robust bounded job start scheduling for Royal Mail delivery offices," Journal of Scheduling, Springer, vol. 24(2), pages 237-258, April.
    2. Wang, Zhuolin & You, Keyou & Song, Shiji & Zhang, Yuli, 2020. "Wasserstein distributionally robust shortest path problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 31-43.
    3. Shaojian Qu & Yuting Xu & Ying Ji & Can Feng & Jinpeng Wei & Shan Jiang, 2022. "Data-Driven Robust Data Envelopment Analysis for Evaluating the Carbon Emissions Efficiency of Provinces in China," Sustainability, MDPI, vol. 14(20), pages 1-26, October.
    4. Sergey S. Ketkov, 2023. "On the Multistage Shortest Path Problem Under Distributional Uncertainty," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 277-308, April.
    5. Shaojian Qu & Yefan Han & Zhong Wu & Hassan Raza, 2021. "Consensus Modeling with Asymmetric Cost Based on Data-Driven Robust Optimization," Group Decision and Negotiation, Springer, vol. 30(6), pages 1395-1432, December.
    6. Luo, Chunling & Tan, Chin Hon & Liu, Xiao, 2020. "Maximum excess dominance: Identifying impractical solutions in linear problems with interval coefficients," European Journal of Operational Research, Elsevier, vol. 282(2), pages 660-676.
    7. Enrico Bartolini & Dominik Goeke & Michael Schneider & Mengdie Ye, 2021. "The Robust Traveling Salesman Problem with Time Windows Under Knapsack-Constrained Travel Time Uncertainty," Transportation Science, INFORMS, vol. 55(2), pages 371-394, March.
    8. Seulgi Joung & Seyoung Oh & Kyungsik Lee, 2023. "Comparative analysis of linear programming relaxations for the robust knapsack problem," Annals of Operations Research, Springer, vol. 323(1), pages 65-78, April.
    9. Lee, Jisun & Joung, Seulgi & Lee, Kyungsik, 2022. "A fully polynomial time approximation scheme for the probability maximizing shortest path problem," European Journal of Operational Research, Elsevier, vol. 300(1), pages 35-45.
    10. Zhang, Pengfei & Gupta, Diwakar, 2023. "Robust optimization with order statistic uncertainty set," European Journal of Operational Research, Elsevier, vol. 311(3), pages 1023-1039.
    11. Groß, Patrick-Oliver & Ehmke, Jan Fabian & Mattfeld, Dirk Christian, 2020. "Interval travel times for robust synchronization in city logistics vehicle routing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    12. Shaojian Qu & Can Feng & Shan Jiang & Jinpeng Wei & Yuting Xu, 2022. "Data-Driven Robust DEA Models for Measuring Operational Efficiency of Endowment Insurance System of Different Provinces in China," Sustainability, MDPI, vol. 14(16), pages 1-21, August.
    13. Goerigk, Marc & Hartisch, Michael, 2023. "A framework for inherently interpretable optimization models," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1312-1324.
    14. Goerigk, Marc & Khosravi, Mohammad, 2023. "Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective," European Journal of Operational Research, Elsevier, vol. 310(2), pages 529-551.

    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. Chassein, André & Goerigk, Marc, 2018. "Variable-sized uncertainty and inverse problems in robust optimization," European Journal of Operational Research, Elsevier, vol. 264(1), pages 17-28.
    2. Chassein, André & Goerigk, Marc, 2018. "Compromise solutions for robust combinatorial optimization with variable-sized uncertainty," European Journal of Operational Research, Elsevier, vol. 269(2), pages 544-555.
    3. Chassein, André & Goerigk, Marc, 2017. "Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 58-69.
    4. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    5. Jannis Kurtz, 2018. "Robust combinatorial optimization under budgeted–ellipsoidal uncertainty," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 315-337, December.
    6. Artur Alves Pessoa & Michael Poss & Ruslan Sadykov & François Vanderbeck, 2021. "Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty," Operations Research, INFORMS, vol. 69(3), pages 739-754, May.
    7. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    8. Pätzold, Julius & Schöbel, Anita, 2020. "Approximate cutting plane approaches for exact solutions to robust optimization problems," European Journal of Operational Research, Elsevier, vol. 284(1), pages 20-30.
    9. Huan Xu & Constantine Caramanis & Shie Mannor, 2012. "Optimization Under Probabilistic Envelope Constraints," Operations Research, INFORMS, vol. 60(3), pages 682-699, June.
    10. Sally G. Arcidiacono & Damiano Rossello, 2022. "A hybrid approach to the discrepancy in financial performance’s robustness," Operational Research, Springer, vol. 22(5), pages 5441-5476, November.
    11. Yu, Pengfei & Gao, Ruotian & Xing, Wenxun, 2021. "Maximizing perturbation radii for robust convex quadratically constrained quadratic programs," European Journal of Operational Research, Elsevier, vol. 293(1), pages 50-64.
    12. Fernandes, Betina & Street, Alexandre & Valladão, Davi & Fernandes, Cristiano, 2016. "An adaptive robust portfolio optimization model with loss constraints based on data-driven polyhedral uncertainty sets," European Journal of Operational Research, Elsevier, vol. 255(3), pages 961-970.
    13. Fertis, Apostolos & Baes, Michel & Lüthi, Hans-Jakob, 2012. "Robust risk management," European Journal of Operational Research, Elsevier, vol. 222(3), pages 663-672.
    14. Aharon Ben-Tal & Dimitris Bertsimas & David B. Brown, 2010. "A Soft Robust Model for Optimization Under Ambiguity," Operations Research, INFORMS, vol. 58(4-part-2), pages 1220-1234, August.
    15. Jornada, Daniel & Leon, V. Jorge, 2016. "Robustness methodology to aid multiobjective decision making in the electricity generation capacity expansion problem to minimize cost and water withdrawal," Applied Energy, Elsevier, vol. 162(C), pages 1089-1108.
    16. Algo Carè & Simone Garatti & Marco C. Campi, 2014. "FAST---Fast Algorithm for the Scenario Technique," Operations Research, INFORMS, vol. 62(3), pages 662-671, June.
    17. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    18. Sandra Cruz Caçador & Pedro Manuel Cortesão Godinho & Joana Maria Pina Cabral Matos Dias, 2022. "A minimax regret portfolio model based on the investor’s utility loss," Operational Research, Springer, vol. 22(1), pages 449-484, March.
    19. Güray Kara & Ayşe Özmen & Gerhard-Wilhelm Weber, 2019. "Stability advances in robust portfolio optimization under parallelepiped uncertainty," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 241-261, March.
    20. Gülpınar, Nalan & Pachamanova, Dessislava & Çanakoğlu, Ethem, 2013. "Robust strategies for facility location under uncertainty," European Journal of Operational Research, Elsevier, vol. 225(1), pages 21-35.

    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:eee:ejores:v:274:y:2019:i:2:p:671-686. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.