IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v47y2013i2p247-265.html
   My bibliography  Save this article

A Reference Point Approach for the Resource Constrained Shortest Path Problems

Author

Listed:
  • Luigi Di Puglia Pugliese

    (Department of Electronics, Computer Science and Systems, University of Calabria, Rende (CS), Italy)

  • Francesca Guerriero

    (Department of Electronics, Computer Science and Systems, University of Calabria, Rende (CS), Italy)

Abstract

The Resource Constrained Shortest Path Problem ((R-script) (C-script) (S-script) (P-script) (P-script)) is a variant of the classical shortest path problem and is of great practical importance. The aim is to find the shortest path between a given pair of nodes under additional constraints representing upper bounds on the consumption of resources along the path. In the scientific literature, different approaches have been defined to solve the (R-script) (C-script) (S-script) (P-script) (P-script). In this work we propose an innovative interactive method to address the (R-script) (C-script) (S-script) (P-script) (P-script), based on a novel search strategy of the criteria space. The performance of the proposed approach is evaluated on the basis of an extensive computational study by considering benchmark instances. A comparison with the state-of-the-art approaches developed for the (R-script) (C-script) (S-script) (P-script) (P-script) is also carried out. The computational results have shown that the developed solution strategy is competitive with the most efficient strategies known thus far.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:47:y:2013:i:2:p:247-265
    DOI: 10.1287/trsc.1120.0418
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1120.0418
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1120.0418?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
    ---><---

    References listed on IDEAS

    as
    1. Namorado Climaco, Joao Carlos & Queiros Vieira Martins, Ernesto, 1982. "A bicriterion shortest path algorithm," European Journal of Operational Research, Elsevier, vol. 11(4), pages 399-404, December.
    2. Cynthia Barnhart & Natashia L. Boland & Lloyd W. Clarke & Ellis L. Johnson & George L. Nemhauser & Rajesh G. Shenoi, 1998. "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, INFORMS, vol. 32(3), pages 208-220, August.
    3. Luque, Mariano & Miettinen, Kaisa & Eskelinen, Petri & Ruiz, Francisco, 2009. "Incorporating preference information in interactive reference point methods for multiobjective optimization," Omega, Elsevier, vol. 37(2), pages 450-462, April.
    4. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    5. Arthur Warburton, 1987. "Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems," Operations Research, INFORMS, vol. 35(1), pages 70-79, February.
    6. D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model," Transportation Science, INFORMS, vol. 42(3), pages 263-278, August.
    7. Carraway, Robert L. & Morin, Thomas L. & Moskowitz, Herbert, 1990. "Generalized dynamic programming for multicriteria optimization," European Journal of Operational Research, Elsevier, vol. 44(1), pages 95-104, January.
    8. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    9. Granat, Janusz & Guerriero, Francesca, 2003. "The interactive analysis of the multicriteria shortest path problem by the reference point method," European Journal of Operational Research, Elsevier, vol. 151(1), pages 103-118, November.
    10. Modesti, Paola & Sciomachen, Anna, 1998. "A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 111(3), pages 495-508, December.
    11. Mote, John & Murthy, Ishwar & Olson, David L., 1991. "A parametric approach to solving bicriterion shortest path problems," European Journal of Operational Research, Elsevier, vol. 53(1), pages 81-92, July.
    12. Buchanan, John & Gardiner, Lorraine, 2003. "A comparison of two reference point methods in multiple objective mathematical programming," European Journal of Operational Research, Elsevier, vol. 149(1), pages 17-34, August.
    13. Tung Tung, Chi & Lin Chew, Kim, 1992. "A multicriteria Pareto-optimal path algorithm," European Journal of Operational Research, Elsevier, vol. 62(2), pages 203-209, October.
    14. Murthy, Ishwar & Olson, David L., 1994. "An interactive procedure using domination cones for bicriterion shortest path problems," European Journal of Operational Research, Elsevier, vol. 72(2), pages 417-431, January.
    15. W Ogryczak, 2001. "On goal programming formulations of the reference point method," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(6), pages 691-698, June.
    16. 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.
    17. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    18. Elimam, A. A. & Kohler, David, 1997. "Two engineering applications of a constrained shortest-path model," European Journal of Operational Research, Elsevier, vol. 103(3), pages 426-438, December.
    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. Trivella, Alessio & Corman, Francesco & Koza, David F. & Pisinger, David, 2021. "The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    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. 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.
    4. 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.
    5. Matthias Ruß & Gunther Gust & Dirk Neumann, 2021. "The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks," Operations Research, INFORMS, vol. 69(3), pages 709-726, May.
    6. Chen, Bi Yu & Chen, Xiao-Wei & Chen, Hui-Ping & Lam, William H.K., 2020. "Efficient algorithm for finding k shortest paths based on re-optimization technique," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    7. L. Di Puglia Pugliese & D. Ferone & P. Festa & F. Guerriero, 2022. "A generalized shortest path tour problem with time windows," Computational Optimization and Applications, Springer, vol. 83(2), pages 593-614, November.
    8. Antonio Frangioni & Laura Galli & Maria Grazia Scutellà, 2015. "Delay-Constrained Shortest Paths: Approximation Algorithms and Second-Order Cone Models," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 1051-1077, March.
    9. 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.
    10. 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.

    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. Opasanon, Sathaporn & Miller-Hooks, Elise, 2006. "Multicriteria adaptive paths in stochastic, time-varying networks," European Journal of Operational Research, Elsevier, vol. 173(1), pages 72-91, August.
    2. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    3. Soroush, H.M., 2008. "Optimal paths in bi-attribute networks with fractional cost functions," European Journal of Operational Research, Elsevier, vol. 190(3), pages 633-658, November.
    4. F. Guerriero & R. Musmanno, 2001. "Label Correcting Methods to Solve Multicriteria Shortest Path Problems," Journal of Optimization Theory and Applications, Springer, vol. 111(3), pages 589-613, December.
    5. Granat, Janusz & Guerriero, Francesca, 2003. "The interactive analysis of the multicriteria shortest path problem by the reference point method," European Journal of Operational Research, Elsevier, vol. 151(1), pages 103-118, November.
    6. 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.
    7. Faramroze G. Engineer & George L. Nemhauser & Martin W. P. Savelsbergh, 2011. "Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 105-119, February.
    8. 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.
    9. 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.
    10. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    11. 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.
    12. Li, Jianping & Ge, Yu & He, Shuai & Lichen, Junran, 2014. "Approximation algorithms for constructing some required structures in digraphs," European Journal of Operational Research, Elsevier, vol. 232(2), pages 307-314.
    13. Strehler, Martin & Merting, Sören & Schwan, Christian, 2017. "Energy-efficient shortest routes for electric and hybrid vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 111-135.
    14. Michael Zabarankin & Stan Uryasev & Robert Murphey, 2006. "Aircraft routing under the risk of detection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(8), pages 728-747, December.
    15. Li Guan & Jianping Li & Weidong Li & Junran Lichen, 2019. "Improved approximation algorithms for the combination problem of parallel machine scheduling and path," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 689-697, October.
    16. Duque, Daniel & Lozano, Leonardo & Medaglia, Andrés L., 2015. "An exact method for the biobjective shortest path problem for large-scale road networks," European Journal of Operational Research, Elsevier, vol. 242(3), pages 788-797.
    17. Avella, Pasquale & Boccia, Maurizio & Sforza, Antonio, 2002. "A penalty function heuristic for the resource constrained shortest path problem," European Journal of Operational Research, Elsevier, vol. 142(2), pages 221-230, October.
    18. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    19. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    20. de Lima Pinto, Leizer & Bornstein, Cláudio Thomás & Maculan, Nelson, 2009. "The tricriterion shortest path problem with at least two bottleneck objective functions," European Journal of Operational Research, Elsevier, vol. 198(2), pages 387-391, October.

    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:inm:ortrsc:v:47:y:2013:i:2:p:247-265. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.