IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v41y2007i7p756-771.html
   My bibliography  Save this article

An improved solution algorithm for the constrained shortest path problem

Author

Listed:
  • Santos, Luis
  • Coutinho-Rodrigues, João
  • Current, John R.

Abstract

The shortest path problem is one of the classic network problems. The objective of this problem is to identify the least cost path through a network from a pre-determined starting node to a pre-determined terminus node. It has many practical applications and can be solved optimally via efficient algorithms. Numerous modifications of the problem exist. In general, these are more difficult to solve. One of these modified versions includes an additional constraint that establishes an upper limit on the sum of some other arc cost (e.g., travel time) for the path. In this paper, a new optimal algorithm for this constrained shortest path problem is introduced. Extensive computational tests are presented which compare the algorithm to the two most commonly used algorithms to solve it. The results indicate that the new algorithm can solve optimally very large problem instances and is generally superior to the previous ones in terms of solution time and computer memory requirements. This is particularly true for the problem instances that are most difficult to solve. That is, those on large networks and/or where the additional constraint is most constraining.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:41:y:2007:i:7:p:756-771
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(07)00012-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Stuart E. Dreyfus, 1969. "An Appraisal of Some Shortest-Path Algorithms," Operations Research, INFORMS, vol. 17(3), pages 395-412, June.
    2. de Queiros Vieira Martins, Ernesto, 1984. "An algorithm for ranking paths that may contain cycles," European Journal of Operational Research, Elsevier, vol. 18(1), pages 123-130, October.
    3. Azevedo, JoseAugusto & Santos Costa, Maria Emilia O. & Silvestre Madeira, Joaquim Joao E. R. & Vieira Martins, Ernesto Q., 1993. "An algorithm for the ranking of shortest paths," European Journal of Operational Research, Elsevier, vol. 69(1), pages 97-106, August.
    4. 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.
    5. George B. Dantzig, 1960. "On the Shortest Route Through a Network," Management Science, INFORMS, vol. 6(2), pages 187-190, January.
    6. John Current & Hasan Pirkul & Erik Rolland, 1994. "Efficient Algorithms for Solving the Shortest Covering Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 317-327, 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. 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.
    2. Li, Xiangyong & Lin, Shaochong & Tian, Peng & Aneja, Y.P., 2017. "Models and column generation approach for the resource-constrained minimum cost path problem with relays," Omega, Elsevier, vol. 66(PA), pages 79-90.
    3. Marinakis, Yannis & Migdalas, Athanasios & Sifaleras, Angelo, 2017. "A hybrid Particle Swarm Optimization – Variable Neighborhood Search algorithm for Constrained Shortest Path problems," European Journal of Operational Research, Elsevier, vol. 261(3), pages 819-834.
    4. 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.
    5. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    6. 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.
    7. Qian Ye & Hyun Kim, 2019. "Partial Node Failure in Shortest Path Network Problems," Sustainability, MDPI, vol. 11(22), pages 1-21, November.
    8. Axel Parmentier, 2019. "Algorithms for non-linear and stochastic resource constrained shortest path," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(2), pages 281-317, April.
    9. 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.
    10. Shi, Ning & Zhou, Shaorui & Wang, Fan & Tao, Yi & Liu, Liming, 2017. "The multi-criteria constrained shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 13-29.
    11. Himmich, Ilyas & El Hallaoui, Issmail & Soumis, François, 2024. "A multiphase dynamic programming algorithm for the shortest path problem with resource constraints," European Journal of Operational Research, Elsevier, vol. 315(2), pages 470-483.
    12. Walteros, Jose L. & Vogiatzis, Chrysafis & Pasiliao, Eduardo L. & Pardalos, Panos M., 2014. "Integer programming models for the multidimensional assignment problem with star costs," European Journal of Operational Research, Elsevier, vol. 235(3), pages 553-568.
    13. Lowry, Michael B. & Furth, Peter & Hadden-Loh, Tracy, 2016. "Prioritizing new bicycle facilities to improve low-stress network connectivity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 86(C), pages 124-140.
    14. Santos, Luís & Coutinho-Rodrigues, João & Current, John R., 2010. "An improved ant colony optimization based algorithm for the capacitated arc routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 246-266, February.
    15. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    16. Mark M. Nejad & Lena Mashayekhy & Daniel Grosu & Ratna Babu Chinnam, 2017. "Optimal Routing for Plug-In Hybrid Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1304-1325, November.
    17. David Corredor-Montenegro & Nicolás Cabrera & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2021. "On the shortest $$\alpha$$ α -reliable path problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 287-318, April.
    18. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    6. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.
    7. Volgenant, A., 2002. "Solving some lexicographic multi-objective combinatorial problems," European Journal of Operational Research, Elsevier, vol. 139(3), pages 578-584, June.
    8. Su, Jason G. & Winters, Meghan & Nunes, Melissa & Brauer, Michael, 2010. "Designing a route planner to facilitate and promote cycling in Metro Vancouver, Canada," Transportation Research Part A: Policy and Practice, Elsevier, vol. 44(7), pages 495-505, August.
    9. Bruno, Giuseppe & Ghiani, Gianpaolo & Improta, Gennaro, 1998. "A multi-modal approach to the location of a rapid transit line," European Journal of Operational Research, Elsevier, vol. 104(2), pages 321-332, January.
    10. Gutierrez, Genaro J. & Kouvelis, Panagiotis & Kurawarwala, Abbas A., 1996. "A robustness approach to uncapacitated network design problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 362-376, October.
    11. Petersen, E. R. & Taylor, A. J., 2001. "An investment planning model for a new North-Central railway in Brazil," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(9), pages 847-862, November.
    12. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    13. Cipriani, Ernesto & Fusco, Gaetano, 2004. "Combined signal setting design and traffic assignment problem," European Journal of Operational Research, Elsevier, vol. 155(3), pages 569-583, June.
    14. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    15. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    16. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    17. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    18. Kurmankhojayev, Daniyar & Li, Guoyuan & Chen, Anthony, 2024. "Link criticality index: Refinement, framework extension, and a case study," Reliability Engineering and System Safety, Elsevier, vol. 243(C).
    19. Joseph Y. J. Chow & Amelia C. Regan, 2011. "Real Option Pricing of Network Design Investments," Transportation Science, INFORMS, vol. 45(1), pages 50-63, February.
    20. Nader Naderializadeh & Kevin A. Crowe, 2020. "Formulating the integrated forest harvest-scheduling model to reduce the cost of the road-networks," Operational Research, Springer, vol. 20(4), pages 2283-2306, December.

    More about this item

    Statistics

    Access and download statistics

    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:transb:v:41:y:2007:i:7:p:756-771. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.