IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v238y2014i3p685-698.html
   My bibliography  Save this article

Branch-and-cut algorithms for the split delivery vehicle routing problem

Author

Listed:
  • Archetti, Claudia
  • Bianchessi, Nicola
  • Speranza, M. Grazia

Abstract

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.

Suggested Citation

  • Archetti, Claudia & Bianchessi, Nicola & Speranza, M. Grazia, 2014. "Branch-and-cut algorithms for the split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 685-698.
    • Handle: RePEc:eee:ejores:v:238:y:2014:i:3:p:685-698
    DOI: 10.1016/j.ejor.2014.04.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171400352X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.04.026?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. Rafael E. Aleman & Xinhui Zhang & Raymond R. Hill, 2009. "A ring-based diversification scheme for routing problems," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 1(1/2), pages 163-190.
    2. J. M. Belenguer & M. C. Martinez & E. Mota, 2000. "A Lower Bound for the Split Delivery Vehicle Routing Problem," Operations Research, INFORMS, vol. 48(5), pages 801-810, October.
    3. 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.
    4. Claudia Archetti & Martin W. P. Savelsbergh & M. Grazia Speranza, 2006. "Worst-Case Analysis for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 40(2), pages 226-234, May.
    5. C. Archetti & M. G. Speranza & A. Hertz, 2006. "A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 40(1), pages 64-73, February.
    6. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    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. Yangkun Xia & Zhuo Fu & Sang-Bing Tsai & Jiangtao Wang, 2018. "A New TS Algorithm for Solving Low-Carbon Logistics Vehicle Routing Problem with Split Deliveries by Backpack—From a Green Operation Perspective," IJERPH, MDPI, vol. 15(5), pages 1-12, May.
    2. 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.
    3. Fleszar, Krzysztof, 2022. "A MILP model and two heuristics for the Bin Packing Problem with Conflicts and Item Fragmentation," European Journal of Operational Research, Elsevier, vol. 303(1), pages 37-53.
    4. Walaa H. El-Ashmawi & Ahmad Salah & Mahmoud Bekhit & Guoqing Xiao & Khalil Al Ruqeishi & Ahmed Fathalla, 2023. "An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict," Mathematics, MDPI, vol. 11(14), pages 1-28, July.
    5. Gouveia, Luís & Paias, Ana & Ponte, Mafalda, 2023. "The travelling salesman problem with positional consistency constraints: An application to healthcare services," European Journal of Operational Research, Elsevier, vol. 308(3), pages 960-989.
    6. Esmaeilbeigi, Rasul & Mak-Hau, Vicky & Yearwood, John & Nguyen, Vivian, 2022. "The multiphase course timetabling problem," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1098-1119.
    7. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    8. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    9. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    10. Wu, Yuehui & Qureshi, Ali Gul & Yamada, Tadashi, 2022. "Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1113-1127.
    11. Claudia Archetti & Ann Melissa Campbell & M. Grazia Speranza, 2016. "Multicommodity vs. Single-Commodity Routing," Transportation Science, INFORMS, vol. 50(2), pages 461-472, May.
    12. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    13. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    14. Pedro Munari & Martin Savelsbergh, 2020. "A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows," SN Operations Research Forum, Springer, vol. 1(4), pages 1-24, December.
    15. Coelho, Leandro C. & Laporte, Gilbert, 2015. "Classification, models and exact algorithms for multi-compartment delivery problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 854-864.
    16. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    17. Michael Drexl, 2014. "A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints," Working Papers 1412, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Nov 2014.
    18. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    19. Jing Chen & Pengfei Gui & Tao Ding & Sanggyun Na & Yingtang Zhou, 2019. "Optimization of Transportation Routing Problem for Fresh Food by Improved Ant Colony Algorithm Based on Tabu Search," Sustainability, MDPI, vol. 11(23), pages 1-22, November.
    20. Xiaofan Lai & Liang Xu & Zhou Xu & Yang Du, 2023. "An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1179-1194, September.
    21. Hernández-Pérez, Hipólito & Salazar-González, Juan-José, 2022. "A Branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 297(2), pages 467-483.
    22. Huang, Yixiao & Savelsbergh, Martin & Zhao, Lei, 2018. "Designing logistics systems for home delivery in densely populated urban areas," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 95-125.
    23. Yangkun Xia & Zhuo Fu & Lijun Pan & Fenghua Duan, 2018. "Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-19, May.
    24. Grigorios D. Konstantakopoulos & Sotiris P. Gayialis & Evripidis P. Kechagias, 2022. "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Operational Research, Springer, vol. 22(3), pages 2033-2062, July.
    25. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.

    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. Berbotto, Leonardo & García, Sergio & Nogales, Francisco J., 2011. "A vehicle routing model with split delivery and stop nodes," DES - Working Papers. Statistics and Econometrics. WS ws110906, Universidad Carlos III de Madrid. Departamento de Estadística.
    2. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    3. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. 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.
    5. C. Archetti & M. Bouchard & G. Desaulniers, 2011. "Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows," Transportation Science, INFORMS, vol. 45(3), pages 285-298, August.
    6. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    7. Lin, Yen-Hung & Batta, Rajan & Rogerson, Peter A. & Blatt, Alan & Flanigan, Marie, 2011. "A logistics model for emergency supply of critical items in the aftermath of a disaster," Socio-Economic Planning Sciences, Elsevier, vol. 45(4), pages 132-145, December.
    8. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    9. 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.
    10. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    11. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.
    12. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    13. José-Manuel Belenguer & Enrique Benavent & Nacima Labadi & Christian Prins & Mohamed Reghioui, 2010. "Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic," Transportation Science, INFORMS, vol. 44(2), pages 206-220, May.
    14. Hertz, Alain & Uldry, Marc & Widmer, Marino, 2012. "Integer linear programming models for a cement delivery problem," European Journal of Operational Research, Elsevier, vol. 222(3), pages 623-631.
    15. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    16. Pedro Munari & Martin Savelsbergh, 2020. "A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows," SN Operations Research Forum, Springer, vol. 1(4), pages 1-24, December.
    17. Belfiore, PatrI´cia & Yoshida Yoshizaki, Hugo Tsugunobu, 2009. "Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil," European Journal of Operational Research, Elsevier, vol. 199(3), pages 750-758, December.
    18. Nicola Bianchessi & Michael Drexl & Stefan Irnich, 2019. "The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints," Transportation Science, INFORMS, vol. 53(4), pages 1067-1084, March.
    19. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    20. Nicola Bianchessi & Stefan Irnich, 2019. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 53(2), pages 442-462, March.

    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:ejores:v:238:y:2014:i:3:p:685-698. 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/locate/eor .

    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.