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

An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints

Author

Listed:
  • Leonardo Lozano

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Daniel Duque

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Andrés L. Medaglia

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

Abstract

The elementary shortest path problem with resource constraints (ESPPRC) is an NP-hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state-of-the-art algorithms for the ESPPRC on the well-known Solomon’s test bed for the VRPTW.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:50:y:2016:i:1:p:348-357
    DOI: 10.1287/trsc.2014.0582
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2014.0582
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2014.0582?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. Louis-Martin Rousseau & Michel Gendreau & Gilles Pesant & Filippo Focacci, 2004. "Solving VRPTWs with Constraint Programming Based Column Generation," Annals of Operations Research, Springer, vol. 130(1), pages 199-216, August.
    2. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    3. 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.
    4. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    5. 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.
    6. 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.
    7. Robert E. Bixby, 2002. "Solving Real-World Linear Programs: A Decade and More of Progress," Operations Research, INFORMS, vol. 50(1), pages 3-15, February.
    8. 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.
    9. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    10. 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.
    11. 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. You, Jintao & Wang, Yuan & Xue, Zhaojie, 2023. "An exact algorithm for the multi-trip container drayage problem with truck platooning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    2. 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.
    3. Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    4. 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.
    5. Tian, Xiaopeng & Niu, Huimin, 2020. "Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 143-173.
    6. Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    7. Tresoldi, Emanuele & Malucelli, Federico & Nonato, Maddalena, 2021. "A personalized walking bus service requiring optimized route decisions: A real case," European Journal of Operational Research, Elsevier, vol. 289(3), pages 855-866.
    8. Vital, Filipe & Ioannou, Petros, 2021. "Scheduling and shortest path for trucks with working hours and parking availability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 148(C), pages 1-37.
    9. Jia, Menglei & Chen, Feng, 2023. "Upward scalable vehicle routing problem of automobile inbound logistics with pickup flexibility," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    10. Fazi, Stefano & Choudhary, Sourabh Kumar & Dong, Jing-Xin, 2023. "The multi-trip container drayage problem with synchronization for efficient empty containers re-usage," European Journal of Operational Research, Elsevier, vol. 310(1), pages 343-359.
    11. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.
    12. Lijing Du & Xiaohuan Li & Yuan Gan & Kaijun Leng, 2022. "Optimal Model and Algorithm of Medical Materials Delivery Drone Routing Problem under Major Public Health Emergencies," Sustainability, MDPI, vol. 14(8), pages 1-17, April.
    13. Vital, Filipe & Ioannou, Petros, 2022. "Optimizing Fuel Consumption and Pollutant Emissions in Truck Routing with Parking Availability Prediction and Working Hours Constraints," Institute of Transportation Studies, Working Paper Series qt8rw99523, Institute of Transportation Studies, UC Davis.
    14. Lin, Meiyan & Ma, Lijun & Ying, Chengshuo, 2021. "Matching daily home health-care demands with supply in service-sharing platforms," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    15. Reihaneh, Mohammad & Ansari, Sina & Farhadi, Farbod, 2023. "Patient appointment scheduling at hemodialysis centers: An exact branch and price approach," European Journal of Operational Research, Elsevier, vol. 309(1), pages 35-52.
    16. 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.

    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. 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.
    3. 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.
    4. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, 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. 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.
    7. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    8. 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.
    9. 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.
    10. Claudia Bode & Stefan Irnich, 2012. "Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem," Operations Research, INFORMS, vol. 60(5), pages 1167-1182, October.
    11. Christian Tilk & Ann-Kathrin Rothenbächer & Timo Gschwind & Stefan Irnich, 2016. "Asymmetry Helps: Dynamic Half-Way Points for Solving Shortest Path Problems with Resource Constraints Faster," Working Papers 1615, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    12. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    13. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    14. Timo Gschwind & Stefan Irnich, 2015. "Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 49(2), pages 335-354, May.
    15. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.
    16. Marilène Cherkesly & Guy Desaulniers & Gilbert Laporte, 2015. "Branch-Price-and-Cut Algorithms for the Pickup and Delivery Problem with Time Windows and Last-in-First-Out Loading," Transportation Science, INFORMS, vol. 49(4), pages 752-766, November.
    17. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    18. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    20. 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.

    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:50:y:2016:i:1:p:348-357. 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.