IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v63y2016i2p559-583.html
   My bibliography  Save this article

On the shortest path problem with negative cost cycles

Author

Listed:
  • Luigi Di Puglia Pugliese
  • Francesca Guerriero

Abstract

In this paper, the elementary single-source all-destinations shortest path problem is considered. Given a directed graph, containing negative cost cycles, the aim is to find paths with minimum cost from a source node to each other node, that do not contain repeated nodes. Two solution strategies are proposed to solve the problem under investigation and their theoretical properties are investigated. The first is a dynamic programming approach, the second method is based on the solution of the k shortest paths problem, where k is considered as a variable. Theoretical aspects related to the innovative proposed strategies to solve the problem at hand are investigated. The practical behaviour of the defined algorithms is evaluated by considering random generated networks and instances derived from vehicle routing benchmark test problems. Copyright Springer Science+Business Media New York 2016

Suggested Citation

  • Luigi Di Puglia Pugliese & Francesca Guerriero, 2016. "On the shortest path problem with negative cost cycles," Computational Optimization and Applications, Springer, vol. 63(2), pages 559-583, March.
    • Handle: RePEc:spr:coopap:v:63:y:2016:i:2:p:559-583
    DOI: 10.1007/s10589-015-9773-1
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-015-9773-1
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-015-9773-1?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. Luigi Di Puglia Pugliese & Francesca Guerriero, 2013. "A Reference Point Approach for the Resource Constrained Shortest Path Problems," Transportation Science, INFORMS, vol. 47(2), pages 247-265, May.
    2. M. R. Rao, 1980. "Technical Note—A Note on the Multiple Traveling Salesmen Problem," Operations Research, INFORMS, vol. 28(3-part-i), pages 628-632, June.
    3. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    4. Di Puglia Pugliese, Luigi & Guerriero, Francesca, 2013. "Shortest path problem with forbidden paths: The elementary version," European Journal of Operational Research, Elsevier, vol. 227(2), pages 254-267.
    5. D. Klingman & A. Napier & J. Stutz, 1974. "NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, INFORMS, vol. 20(5), pages 814-821, January.
    6. Bezalel Gavish & Kizhanathan Srikanth, 1986. "An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems," Operations Research, INFORMS, vol. 34(5), pages 698-717, October.
    7. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    8. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    9. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    10. Marshall L. Fisher, 1994. "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees," Operations Research, INFORMS, vol. 42(4), pages 626-642, August.
    11. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.
    12. Stuart E. Dreyfus, 1969. "An Appraisal of Some Shortest-Path Algorithms," Operations Research, INFORMS, vol. 17(3), pages 395-412, June.
    13. Luigi Di Puglia Pugliese & Francesca Guerriero, 2012. "A computational study of solution approaches for the resource constrained elementary shortest path problem," Annals of Operations Research, Springer, vol. 201(1), pages 131-157, December.
    14. George B. Dantzig, 1960. "On the Shortest Route Through a Network," Management Science, INFORMS, vol. 6(2), pages 187-190, January.
    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. Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    2. Rafael Castro Andrade & Rommel Dias Saraiva, 2020. "MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles," Annals of Operations Research, Springer, vol. 286(1), pages 147-172, March.
    3. Peng, Xu & Tao, Xiaoma, 2018. "Cooperative game of electricity retailers in China's spot electricity market," Energy, Elsevier, vol. 145(C), pages 152-170.

    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. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.
    2. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    3. Melchiori, Anna & Sgalambro, Antonino, 2020. "A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 846-857.
    4. Santos, Luis & Coutinho-Rodrigues, João & Current, John R., 2007. "An improved solution algorithm for the constrained shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 756-771, August.
    5. José Alejandro Cornejo-Acosta & Jesús García-Díaz & Julio César Pérez-Sansalvador & Carlos Segura, 2023. "Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems," Mathematics, MDPI, vol. 11(13), pages 1-25, July.
    6. Festa, P. & Guerriero, F. & Laganà, D. & Musmanno, R., 2013. "Solving the shortest path tour problem," European Journal of Operational Research, Elsevier, vol. 230(3), pages 464-474.
    7. Boschetti, Marco Antonio & Maniezzo, Vittorio & Strappaveccia, Francesco, 2017. "Route relaxations on GPU for vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 456-466.
    8. Azar Sadeghnejad-Barkousaraie & Rajan Batta & Moises Sudit, 2017. "Convoy movement problem: a civilian perspective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 14-33, January.
    9. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    10. 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.
    11. Herminia Calvete & Lourdes del-Pozo & José Iranzo, 2012. "Algorithms for the quickest path problem and the reliable quickest path problem," Computational Management Science, Springer, vol. 9(2), pages 255-272, May.
    12. Sandra Zajac, 2018. "On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem," Journal of Heuristics, Springer, vol. 24(3), pages 515-550, June.
    13. Yang, Dingtong & Hyland, Michael F. & Jayakrishnan, R., 2024. "Tackling the crowdsourced shared-trip delivery problem at scale with a novel decomposition heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
    14. Pierre-Léo Bourbonnais & Catherine Morency & Martin Trépanier & Éric Martel-Poliquin, 2021. "Transit network design using a genetic algorithm with integrated road network and disaggregated O–D demand data," Transportation, Springer, vol. 48(1), pages 95-130, February.
    15. P. Festa & F. Guerriero & A. Napoletano, 2019. "An auction-based approach for the re-optimization shortest path tree problem," Computational Optimization and Applications, Springer, vol. 74(3), pages 851-893, December.
    16. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    17. Javier Duran & Lorena Pradenas & Victor Parada, 2019. "Transit network design with pollution minimization," Public Transport, Springer, vol. 11(1), pages 189-210, June.
    18. Wang, Li & Yang, Lixing & Gao, Ziyou, 2016. "The constrained shortest path problem with stochastic correlated link travel times," European Journal of Operational Research, Elsevier, vol. 255(1), pages 43-57.
    19. Sedeño-Noda, Antonio & Alonso-Rodríguez, Sergio, 2015. "An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem," Applied Mathematics and Computation, Elsevier, vol. 265(C), pages 602-618.
    20. Malmborg, Charles J., 1996. "A genetic algorithm for service level based vehicle scheduling," European Journal of Operational Research, Elsevier, vol. 93(1), pages 121-134, August.

    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:coopap:v:63:y:2016:i:2:p:559-583. 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.