IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v60y2014i2p265-287.html
   My bibliography  Save this article

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

Author

Listed:
  • Amadeu Coco
  • João Júnior
  • Thiago Noronha
  • Andréa Santos

Abstract

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Amadeu Coco & João Júnior & Thiago Noronha & Andréa Santos, 2014. "An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem," Journal of Global Optimization, Springer, vol. 60(2), pages 265-287, October.
    • Handle: RePEc:spr:jglopt:v:60:y:2014:i:2:p:265-287
    DOI: 10.1007/s10898-014-0187-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-014-0187-x
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-014-0187-x?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. Virginie Gabrel & Cécile Murat & Lei Wu, 2013. "New models for the robust shortest path problem: complexity, resolution and generalization," Annals of Operations Research, Springer, vol. 207(1), pages 97-120, August.
    2. Gonçalves, J.F. & Mendes, J.J.M. & Resende, M.G.C., 2008. "A genetic algorithm for the resource constrained multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1171-1190, September.
    3. Montemanni, R. & Gambardella, L. M., 2005. "A branch and bound algorithm for the robust spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 161(3), pages 771-779, March.
    4. Stefan Voßs & Andreas Fink & Cees Duin, 2005. "Looking Ahead with the Pilot Method," Annals of Operations Research, Springer, vol. 136(1), pages 285-302, April.
    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. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    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. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    2. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    3. Amadeu Almeida Coco & João Carlos Abreu Júnior & Thiago F. Noronha & Andréa Cynthia Santos, 2017. "Erratum to: An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem," Journal of Global Optimization, Springer, vol. 68(2), pages 463-466, June.
    4. Mehdi Karimi & Somayeh Moazeni & Levent Tunçel, 2018. "A Utility Theory Based Interactive Approach to Robustness in Linear Optimization," Journal of Global Optimization, Springer, vol. 70(4), pages 811-842, April.

    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. Conde, Eduardo, 2012. "On a constant factor approximation for minmax regret problems using a symmetry point scenario," European Journal of Operational Research, Elsevier, vol. 219(2), pages 452-457.
    2. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    3. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    4. Zhang, Yu & Tang, Jiafu, 2018. "A robust optimization approach for itinerary planning with deadline," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 56-74.
    5. Wei Wu & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2022. "An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2523-2539, September.
    6. 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.
    7. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    8. 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.
    9. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    10. Bredael, Dries & Vanhoucke, Mario, 2023. "Multi-project scheduling: A benchmark analysis of metaheuristic algorithms on various optimisation criteria and due dates," European Journal of Operational Research, Elsevier, vol. 308(1), pages 54-75.
    11. Chassein, André & Goerigk, Marc & Kurtz, Jannis & Poss, Michael, 2019. "Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 279(2), pages 308-319.
    12. 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.
    13. Barahimi, Amir Hossein & Eydi, Alireza & Aghaie, Abdolah, 2021. "Multi-modal urban transit network design considering reliability: multi-objective bi-level optimization," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    14. Fernando Ordóñez & Nicolás E. Stier-Moses, 2010. "Wardrop Equilibria with Risk-Averse Users," Transportation Science, INFORMS, vol. 44(1), pages 63-86, February.
    15. Kammerdiner, A.R. & Pasiliao, E.L., 2014. "In and out forests on combinatorial landscapes," European Journal of Operational Research, Elsevier, vol. 236(1), pages 78-84.
    16. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    17. Goel, Asvin & Meisel, Frank, 2013. "Workforce routing and scheduling for electricity network maintenance with downtime minimization," European Journal of Operational Research, Elsevier, vol. 231(1), pages 210-228.
    18. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    19. Kalaı¨, Rim & Lamboray, Claude & Vanderpooten, Daniel, 2012. "Lexicographic α-robustness: An alternative to min–max criteria," European Journal of Operational Research, Elsevier, vol. 220(3), pages 722-728.
    20. repec:wut:journl:v:2:y:2012:id:1022 is not listed on IDEAS
    21. Bogusz Przybysławski & Adam Kasperski, 2012. "A computational study of approximation algorithms for a minmax resource allocation problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 22(2), pages 35-43.

    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:spr:jglopt:v:60:y:2014:i:2:p:265-287. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.