IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v244y2016i2d10.1007_s10479-016-2116-5.html
   My bibliography  Save this article

Exact methods for solving the elementary shortest and longest path problems

Author

Listed:
  • Quoc Trung Bui

    (FPT University)

  • Yves Deville

    (Université catholique de Louvain)

  • Quang Dung Pham

    (Hanoi University of Science and Technology)

Abstract

We consider in this paper the problems of finding the elementary shortest and longest paths on a graph containing negative and positive cycles. These problems are NP-hard. We propose exact algorithms based on mixed integer programming for their solution, employing different valid inequalities. Moreover, we propose decomposition techniques which are very efficient for cases with special structure. Experimental results show the efficiency of our algorithms compared with state of the art exact algorithms.

Suggested Citation

  • Quoc Trung Bui & Yves Deville & Quang Dung Pham, 2016. "Exact methods for solving the elementary shortest and longest path problems," Annals of Operations Research, Springer, vol. 244(2), pages 313-348, September.
    • Handle: RePEc:spr:annopr:v:244:y:2016:i:2:d:10.1007_s10479-016-2116-5
    DOI: 10.1007/s10479-016-2116-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-016-2116-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-016-2116-5?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. Kulkarni, R. V. & Bhave, P. R., 1985. "Integer programming formulations of vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 20(1), pages 58-67, April.
    2. Manfred W. Padberg & M. R. Rao, 1982. "Odd Minimum Cut-Sets and b -Matchings," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 67-80, February.
    3. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    4. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    5. Matteo Fischetti, 1991. "Facets of the Asymmetric Traveling Salesman Polytope," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 42-56, February.
    6. Egon Balas & Sebastián Ceria & Gérard Cornuéjols, 1996. "Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework," Management Science, INFORMS, vol. 42(9), pages 1229-1246, September.
    7. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    8. Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, October.
    9. Michael Drexl & Stefan Irnich, 2012. "Solving Elementary Shortest-Path Problems as Mixed-Integer Programs," Working Papers 1201, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    10. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    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. Moreno, Alfredo & Alem, Douglas & Gendreau, Michel & Munari, Pedro, 2020. "The heterogeneous multicrew scheduling and routing problem in road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 24-58.

    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. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    2. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    3. Timo Hintsch & Stefan Irnich, 2018. "Exact Solution of the Soft-Clustered Vehicle Routing Problem," Working Papers 1813, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    5. Bode, Claudia & Irnich, Stefan, 2014. "The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 415-426.
    6. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    7. Jiliu Li & Zhixing Luo & Roberto Baldacci & Hu Qin & Zhou Xu, 2023. "A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 31-49, January.
    8. Qie He & Stefan Irnich & Yongjia Song, 2018. "Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Working Papers 1804, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Range, Troels Martin, 2013. "Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints," Discussion Papers on Economics 17/2013, University of Southern Denmark, Department of Economics.
    10. Tilk, Christian & Drexl, Michael & Irnich, Stefan, 2019. "Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies," European Journal of Operational Research, Elsevier, vol. 276(2), pages 549-565.
    11. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    12. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    13. Quirion-Blais, Olivier & Chen, Lu, 2021. "A case-based reasoning approach to solve the vehicle routing problem with time windows and drivers’ experience," Omega, Elsevier, vol. 102(C).
    14. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    15. Ahmadi-Javid, Amir & Amiri, Elahe & Meskar, Mahla, 2018. "A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm," European Journal of Operational Research, Elsevier, vol. 271(3), pages 866-881.
    16. Iman Dayarian & Guy Desaulniers, 2019. "A Branch-Price-and-Cut Algorithm for a Production-Routing Problem with Short-Life-Span Products," Transportation Science, INFORMS, vol. 53(3), pages 829-849, May.
    17. Ricardo Fukasawa & Qie He & Fernando Santos & Yongjia Song, 2018. "A Joint Vehicle Routing and Speed Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 694-709, November.
    18. Emilio Zamorano & Annika Becker & Raik Stolletz, 2018. "Task assignment with start time-dependent processing times for personnel at check-in counters," Journal of Scheduling, Springer, vol. 21(1), pages 93-109, February.
    19. Charlotte Vilhelmsen & Richard M. Lusby & Jesper Larsen, 2017. "Tramp ship routing and scheduling with voyage separation requirements," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 913-943, October.
    20. S. Ardizzoni & L. Consolini & M. Laurini & M. Locatelli, 2022. "Shortest path with acceleration constraints: complexity and approximation algorithms," Computational Optimization and Applications, Springer, vol. 83(2), pages 555-592, November.

    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:annopr:v:244:y:2016:i:2:d:10.1007_s10479-016-2116-5. 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.