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

The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints

Author

Listed:
  • Bortfeldt, Andreas
  • Yi, Junmin

Abstract

The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints (3L-SDVRP) combines vehicle routing and three-dimensional loading with additional packing constraints. In the 3L-SDVRP splitting deliveries of customers is basically possible, i.e. a customer can be visited in two or more tours. We examine essential problem features and introduce two problem variants. In the first variant, called 3L-SDVRP with forced splitting, a delivery is only split if the demand of a customer cannot be transported by a single vehicle. In the second variant, termed 3L-SDVRP with optional splitting, splitting customer deliveries can be done any number of times. We propose a hybrid algorithm consisting of a local search algorithm for routing and a genetic algorithm and several construction heuristics for packing. Numerical experiments are conducted using three sets of instances with both industrial and academic origins. One of them was provided by an automotive logistics company in Shanghai; in this case some customers per instance have a total freight volume larger than the loading space of a vehicle. The results prove that splitting deliveries can be beneficial not only in the one-dimensional case but also when goods are modeled as three-dimensional items.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:282:y:2020:i:2:p:545-558
    DOI: 10.1016/j.ejor.2019.09.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719307647
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.09.024?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. 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.
    2. Fuellerer, Guenther & Doerner, Karl F. & Hartl, Richard F. & Iori, Manuel, 2010. "Metaheuristics for vehicle routing problems with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 201(3), pages 751-759, March.
    3. Michel Gendreau & Manuel Iori & Gilbert Laporte & Silvano Martello, 2006. "A Tabu Search Algorithm for a Routing and Container Loading Problem," Transportation Science, INFORMS, vol. 40(3), pages 342-350, August.
    4. Côté, J.F. & Guastaroba, G. & Speranza, M.G., 2017. "The value of integrating loading and routing," European Journal of Operational Research, Elsevier, vol. 257(1), pages 89-105.
    5. 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.
    6. Irnich, S. & Schneider, M. & Vigo, D., 2014. "Four Variants of the Vehicle Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63514, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    7. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2018. "A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1029-1075, October.
    8. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    9. Bruno P. Bruck & Manuel Iori, 2017. "Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries," Operations Research, INFORMS, vol. 65(6), pages 1597-1614, December.
    10. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    11. 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.
    12. 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.
    13. Archetti, Claudia & Savelsbergh, Martin W.P. & Grazia Speranza, M., 2008. "To split or not to split: That is the question," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 114-123, January.
    14. Männel, Dirk & Bortfeldt, Andreas, 2016. "A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 254(3), pages 840-858.
    15. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    16. Bischoff, E. E. & Ratcliff, M. S. W., 1995. "Issues in the development of approaches to container loading," Omega, Elsevier, vol. 23(4), pages 377-390, August.
    17. 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.
    18. Batoul Mahvash & Anjali Awasthi & Satyaveer Chauhan, 2017. "A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1730-1747, March.
    19. Moshe Dror & Pierre Trudeau, 1990. "Split delivery routing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(3), pages 383-402, June.
    20. Reil, Sebastian & Bortfeldt, Andreas & Mönch, Lars, 2018. "Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 266(3), pages 877-894.
    21. Manuel Iori & Silvano Martello, 2010. "Rejoinder on: Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 41-42, July.
    22. Bortfeldt, Andreas & Gehring, Hermann, 2001. "A hybrid genetic algorithm for the container loading problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 143-161, May.
    23. 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.
    24. 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.
    25. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    26. 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.
    27. Emmanouil E. Zachariadis & Christos D. Tarantilis & Chris T. Kiranoudis, 2012. "The Pallet-Packing Vehicle Routing Problem," Transportation Science, INFORMS, vol. 46(3), pages 341-358, August.
    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. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    2. Nima Pourmohammadreza & Mohammad Reza Akbari Jokar, 2023. "A Novel Two-Phase Approach for Optimization of the Last-Mile Delivery Problem with Service Options," Sustainability, MDPI, vol. 15(10), pages 1-25, May.
    3. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    4. Corinna Krebs & Jan Fabian Ehmke, 2023. "Solution validator and visualizer for (combined) vehicle routing and container loading problems," Annals of Operations Research, Springer, vol. 326(1), pages 561-579, July.
    5. Rajaei, Maryam & Moslehi, Ghasem & Reisi-Nafchi, Mohammad, 2022. "The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale," European Journal of Operational Research, Elsevier, vol. 299(2), pages 706-721.
    6. Vitalii Naumov & Michał Pawluś, 2021. "Identifying the Optimal Packing and Routing to Improve Last-Mile Delivery Using Cargo Bicycles," Energies, MDPI, vol. 14(14), pages 1-15, July.
    7. Yuxin Liu & Zihang Qin & Jin Liu, 2023. "An Improved Genetic Algorithm for the Granularity-Based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(15), pages 1-15, July.
    8. Jie Zhang & Yifan Zhu & Xiaobo Li & Mengjun Ming & Weiping Wang & Tao Wang, 2022. "Multi-Trip Time-Dependent Vehicle Routing Problem with Split Delivery," Mathematics, MDPI, vol. 10(19), pages 1-24, September.
    9. Ji, Bin & Zhang, Zheng & Yu, Samson S. & Zhou, Saiqi & Wu, Guohua, 2023. "Modelling and heuristically solving many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1219-1235.
    10. Vincent F. Yu & Hadi Susanto & Yu-Hsuan Yeh & Shih-Wei Lin & Yu-Tsung Huang, 2022. "The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers," Mathematics, MDPI, vol. 10(6), pages 1-22, March.

    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. Rajaei, Maryam & Moslehi, Ghasem & Reisi-Nafchi, Mohammad, 2022. "The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale," European Journal of Operational Research, Elsevier, vol. 299(2), pages 706-721.
    2. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    3. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    4. Alonso, M.T. & Martinez-Sykora, A. & Alvarez-Valdes, R. & Parreño, F., 2022. "The pallet-loading vehicle routing problem with stability constraints," European Journal of Operational Research, Elsevier, vol. 302(3), pages 860-873.
    5. 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.
    6. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    7. Bonet Filella, Guillem & Trivella, Alessio & Corman, Francesco, 2023. "Modeling soft unloading constraints in the multi-drop container loading problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 336-352.
    8. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    9. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2018. "A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1029-1075, October.
    10. 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.
    11. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2017. "A hybrid solution approach for the 3L-VRP with simultaneous delivery and pickups," FEMM Working Papers 170005, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    12. 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.
    13. M. T. Alonso & R. Alvarez-Valdes & F. Parreño, 2020. "A GRASP algorithm for multi container loading problems with practical constraints," 4OR, Springer, vol. 18(1), pages 49-72, March.
    14. Reil, Sebastian & Bortfeldt, Andreas & Mönch, Lars, 2018. "Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 266(3), pages 877-894.
    15. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    16. 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.
    17. Henriette Koch & Maximilian Schlögell & Andreas Bortfeldt, 2020. "A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls," Journal of Scheduling, Springer, vol. 23(1), pages 71-93, February.
    18. Emmanouil E. Zachariadis & Christos D. Tarantilis & Chris T. Kiranoudis, 2017. "Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints," Operational Research, Springer, vol. 17(1), pages 115-143, April.
    19. Galrão Ramos, A. & Oliveira, José F. & Gonçalves, José F. & Lopes, Manuel P., 2016. "A container loading algorithm with static mechanical equilibrium stability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 565-581.
    20. Alonso, M.T. & Alvarez-Valdes, R. & Iori, M. & Parreño, F. & Tamarit, J.M., 2017. "Mathematical models for multicontainer loading problems," Omega, Elsevier, vol. 66(PA), pages 106-117.

    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:282:y:2020:i:2:p:545-558. 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.