IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v145y2021ics1366554520308103.html
   My bibliography  Save this article

A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates

Author

Listed:
  • Yang, Weibo
  • Ke, Liangjun
  • Wang, David Z.W.
  • Lam, Jasmine Siu Lee

Abstract

In this paper, we investigate the vehicle routing problem with release and due dates (VRPRD), which is a new variant of vehicle routing problem (VRP). In the problem, the order required by a customer is available for delivery later than its release date. A penalty cost, called tardiness cost, will be imposed if a customer is served after its due date. The objective of the VRPRD is to minimize the total routing and weighted tardiness costs. To address the problem, we develop an exact branch-price-and-cut algorithm based on the set-partitioning formulation. An effective bidirectional labeling algorithm is proposed to deal with the pricing problem. Numerical studies have verified that the proposed algorithm can obtain the exact optimal solutions for more than 75% of benchmark instances within approximately six minutes on average.

Suggested Citation

  • Yang, Weibo & Ke, Liangjun & Wang, David Z.W. & Lam, Jasmine Siu Lee, 2021. "A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    • Handle: RePEc:eee:transe:v:145:y:2021:i:c:s1366554520308103
    DOI: 10.1016/j.tre.2020.102167
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554520308103
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.102167?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. Reyes, Damián & Erera, Alan L. & Savelsbergh, Martin W.P., 2018. "Complexity of routing problems with release dates and deadlines," European Journal of Operational Research, Elsevier, vol. 266(1), pages 29-34.
    2. Guy Desaulniers, 2010. "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 58(1), pages 179-192, February.
    3. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    4. Rosario Paradiso & Roberto Roberti & Demetrio Laganá & Wout Dullaert, 2020. "An Exact Solution Framework for Multitrip Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 68(1), pages 180-198, January.
    5. Liu, Shixin & Qin, Shujin & Zhang, Ruiyou, 2018. "A branch-and-price algorithm for the multi-trip multi-repairman problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 25-41.
    6. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    7. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    8. Ponboon, Sattrawut & Qureshi, Ali Gul & Taniguchi, Eiichi, 2016. "Branch-and-price algorithm for the location-routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 1-19.
    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. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    11. Archetti, Claudia & Feillet, Dominique & Speranza, M. Grazia, 2015. "Complexity of routing problems with release dates," European Journal of Operational Research, Elsevier, vol. 247(3), pages 797-803.
    12. Archetti, C. & Feillet, D. & Mor, A. & Speranza, M.G., 2020. "Dynamic traveling salesman problem with stochastic release dates," European Journal of Operational Research, Elsevier, vol. 280(3), pages 832-844.
    13. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    14. Lee, Jongsung & Kim, Byung-In & Johnson, Andrew L. & Lee, Kiho, 2014. "The nuclear medicine production and delivery problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 461-472.
    15. Tang, Jiafu & Yu, Yang & Li, Jia, 2015. "An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 114-132.
    16. 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.
    17. Zhen, Lu & Ma, Chengle & Wang, Kai & Xiao, Liyang & Zhang, Wei, 2020. "Multi-depot multi-trip vehicle routing problem with time windows and release dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    18. 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.
    19. İsmail Karaoğlan & Saadettin Erhan Kesen, 2017. "The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 55(2), pages 536-557, 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. Peng, Xiaoshuai & Zhang, Lele & Thompson, Russell G. & Wang, Kangzhou, 2023. "A three-phase heuristic for last-mile delivery with spatial-temporal consolidation and delivery options," International Journal of Production Economics, Elsevier, vol. 266(C).
    2. Zhou, Hang & Qin, Hu & Cheng, Chun & Rousseau, Louis-Martin, 2023. "An exact algorithm for the two-echelon vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 124-150.
    3. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2024. "Electric van-based robot deliveries with en-route charging," European Journal of Operational Research, Elsevier, vol. 317(3), pages 806-826.
    4. Liu, Wenqian & Liu, Lindong & Qi, Xiangtong, 2024. "Drone resupply with multiple trucks and drones for on-time delivery along given truck routes," European Journal of Operational Research, Elsevier, vol. 318(2), pages 457-468.
    5. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    6. Jeanette Schmidt & Christian Tilk & Stefan Irnich, 2023. "Exact Solution of the Vehicle Routing Problem With Drones," Working Papers 2311, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    7. João Luiz Marques Andrade & Gustavo Campos Menezes, 2023. "A column generation-based heuristic to solve the integrated planning, scheduling, yard allocation and berth allocation problem in bulk ports," Journal of Heuristics, Springer, vol. 29(1), pages 39-76, February.
    8. Qin, Hu & Su, E. & Wang, Yilun & Li, Jiliu, 2022. "Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems," Omega, Elsevier, vol. 109(C).
    9. Tiniç, Gizem Ozbaygin & Karasan, Oya E. & Kara, Bahar Y. & Campbell, James F. & Ozel, Aysu, 2023. "Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 81-123.
    10. Soares, Gabriel & Bulhões, Teobaldo & Bruck, Bruno, 2024. "An efficient hybrid genetic algorithm for the traveling salesman problem with release dates," European Journal of Operational Research, Elsevier, vol. 318(1), pages 31-42.
    11. Fang, Chao & Han, Zonglei & Wang, Wei & Zio, Enrico, 2023. "Routing UAVs in landslides Monitoring: A neural network heuristic for team orienteering with mandatory visits," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    12. Yan, Rui & Zhu, Xiaoping & Zhu, Xiaoning & Peng, Rui, 2023. "Joint optimisation of task abortions and routes of truck-and-drone systems under random attacks," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    13. Ren, Xuan & Froger, Aurélien & Jabali, Ola & Liang, Gongqian, 2024. "A competitive heuristic algorithm for vehicle routing problems with drones," European Journal of Operational Research, Elsevier, vol. 318(2), pages 469-485.
    14. Salama, Mohamed R. & Srinivas, Sharan, 2022. "Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    15. Zhu, Waiming & Hu, Xiaoxuan & Pei, Jun & Pardalos, Panos M., 2024. "Minimizing the total travel distance for the locker-based drone delivery: A branch-and-cut-based method," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).

    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. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    2. Stefan Faldum & Timo Gschwind & Stefan Irnich, 2023. "Subset-Row Inequalities and Unreachability in Path-based Formulations for Routing and Scheduling Problems," Working Papers 2310, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    3. Pina-Pardo, Juan C. & Silva, Daniel F. & Smith, Alice E. & Gatica, Ricardo A., 2024. "Fleet resupply by drones for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 168-182.
    4. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    5. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    6. 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.
    7. Yu, Bin & Shan, Wenxuan & Sheu, Jiuh-Biing & Diabat, Ali, 2022. "Branch-and-price for a combined order selection and distribution problem in online community group-buying of perishable products," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 341-373.
    8. 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.
    9. Huang, Nan & Li, Jiliu & Zhu, Wenbin & Qin, Hu, 2021. "The multi-trip vehicle routing problem with time windows and unloading queue at depot," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    10. Gschwind, Timo & Bianchessi, Nicola & Irnich, Stefan, 2019. "Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 91-104.
    11. Hoogendoorn, Y.N. & Dalmeijer, K., 2021. "Resource-robust valid inequalities for set covering and set partitioning models," Econometric Institute Research Papers EI 2020-08, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    12. Katrin Heßler & Stefan Irnich, 2023. "Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 50-65, January.
    13. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    14. Katrin Heßler & Stefan Irnich, 2021. "Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem," Working Papers 2115, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Schmidt, Jeanette & Tilk, Christian & Irnich, Stefan, 2024. "Using public transport in a 2-echelon last-mile delivery network," European Journal of Operational Research, Elsevier, vol. 317(3), pages 827-840.
    16. Zhen, Lu & Ma, Chengle & Wang, Kai & Xiao, Liyang & Zhang, Wei, 2020. "Multi-depot multi-trip vehicle routing problem with time windows and release dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    17. Annelieke C. Baller & Said Dabia & Wout E. H. Dullaert & Daniele Vigo, 2020. "The Vehicle Routing Problem with Partial Outsourcing," Transportation Science, INFORMS, vol. 54(4), pages 1034-1052, July.
    18. Yang, Yu & Yan, Chiwei & Cao, Yufeng & Roberti, Roberto, 2023. "Planning robust drone-truck delivery routes under road traffic uncertainty," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1145-1160.
    19. Qin, Hu & Su, E. & Wang, Yilun & Li, Jiliu, 2022. "Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems," Omega, Elsevier, vol. 109(C).
    20. 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.

    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:transe:v:145:y:2021:i:c:s1366554520308103. 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/600244/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.