{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T08:03:29Z","timestamp":1782029009600,"version":"3.54.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100014736","name":"Lingnan University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014736","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Memetic Comp."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) is a complex capacitated vehicle routing problem variant that considers split delivery and three-dimensional loading. It aims to determine the optimal routes for a fleet of vehicles by minimizing the number of vehicles required and the total travel distance. However, current methods are limited in efficiency and often yield suboptimal solutions. More efficient and effective methods are needed. Building on a state-of-the-art algorithm for solving the 3L-SDVRP, this paper proposes a more efficient algorithm with several novel features. Firstly, improvements to the packing method are introduced to enhance the loading performance and reduce required vehicles. Secondly, three new search operators are proposed to exploit problem characteristics in order to improve search efficiency significantly. Thirdly, a new adaptive splitting strategy dynamically decides when to split boxes according to the current status of the vehicle and node, thereby reducing computational costs. Lastly, the algorithm includes a new post-optimization method to further improve the solution quality. Extensive experiments validate that our proposed method efficiently reduces the number of required vehicles with fewer computational resources. The effectiveness of each novel component has also been confirmed through ablation experiments.<\/jats:p>","DOI":"10.1007\/s12293-025-00451-9","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T02:24:48Z","timestamp":1744856688000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An efficient local search algorithm for split delivery vehicle routing problem with three-dimensional loading"],"prefix":"10.1007","volume":"17","author":[{"given":"Han","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qing","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"issue":"3","key":"451_CR1","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s10732-008-9101-3","volume":"16","author":"RE Aleman","year":"2010","unstructured":"Aleman RE, Zhang X, Hill RR (2010) An adaptive memory algorithm for the split delivery vehicle routing problem. J Heuristics 16(3):441\u2013473","journal-title":"J Heuristics"},{"issue":"4","key":"451_CR2","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/0305-0483(83)90033-6","volume":"11","author":"JE Beasley","year":"1983","unstructured":"Beasley JE (1983) Route first-cluster second methods for vehicle routing. Omega 11(4):403\u2013408","journal-title":"Omega"},{"key":"451_CR3","unstructured":"Blazinskas A, Misevicius A (2011) Combining 2-opt, 3-opt and 4-opt with k-swap-kick perturbations for the traveling salesman problem. Kaunas University of Technology, Department of Multimedia Engineering, Studentu St pp 50\u2013401. https:\/\/isd.ktu.lt\/it2011\/material\/Proceedings\/1_AI_5.pdf"},{"issue":"1","key":"451_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0377-2217(00)00055-2","volume":"131","author":"A Bortfeldt","year":"2001","unstructured":"Bortfeldt A, Gehring H (2001) A hybrid genetic algorithm for the container loading problem. Eur J Oper Res 131(1):143\u2013161","journal-title":"Eur J Oper Res"},{"issue":"2","key":"451_CR5","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/j.ejor.2019.09.024","volume":"282","author":"A Bortfeldt","year":"2020","unstructured":"Bortfeldt A, Yi J (2020) The split delivery vehicle routing problem with three-dimensional loading constraints. Eur J Oper Res 282(2):545\u2013558","journal-title":"Eur J Oper Res"},{"issue":"2","key":"451_CR6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10732-011-9162-6","volume":"19","author":"S Ceschia","year":"2013","unstructured":"Ceschia S, Schaerf A (2013) Local search for a multi-drop multi-container loading problem. J Heuristics 19(2):275\u2013294","journal-title":"J Heuristics"},{"issue":"4","key":"451_CR7","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1016\/j.cie.2013.07.025","volume":"66","author":"S Ceschia","year":"2013","unstructured":"Ceschia S, Schaerf A, St\u00fctzle T (2013) Local search techniques for a routing-packing problem. Comput Indus Eng 66(4):1138\u20131149","journal-title":"Comput Indus Eng"},{"issue":"17","key":"451_CR8","doi-asserted-by":"publisher","first-page":"6987","DOI":"10.3390\/su12176987","volume":"12","author":"Z Chen","year":"2020","unstructured":"Chen Z, Yang M, Guo Y et al (2020) The split delivery vehicle routing problem with three-dimensional loading and time windows constraints. Sustainability 12(17):6987","journal-title":"Sustainability"},{"issue":"4","key":"451_CR9","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/j.cor.2010.09.010","volume":"38","author":"C Duhamel","year":"2011","unstructured":"Duhamel C, Lacomme P, Prodhon C (2011) Efficient frameworks for greedy split and new depth first search split procedures for routing problems. Comput Operations Res 38(4):723\u2013739","journal-title":"Comput Operations Res"},{"issue":"1","key":"451_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10479-020-03540-9","volume":"291","author":"R El-Hajj","year":"2020","unstructured":"El-Hajj R, Guibadj RN, Moukrim A et al (2020) A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit. Ann Oper Res 291(1):281\u2013316","journal-title":"Ann Oper Res"},{"issue":"3","key":"451_CR11","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1287\/trsc.1050.0145","volume":"40","author":"M Gendreau","year":"2006","unstructured":"Gendreau M, Iori M, Laporte G et al (2006) A tabu search algorithm for a routing and container loading problem. Transp Sci 40(3):342\u2013350","journal-title":"Transp Sci"},{"issue":"1","key":"451_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10479-014-1777-1","volume":"234","author":"ZH Hu","year":"2015","unstructured":"Hu ZH, Zhao Y, Tao S et al (2015) Finished-vehicle transporter routing problem solved by loading pattern discovery. Ann Oper Res 234(1):37\u201356","journal-title":"Ann Oper Res"},{"issue":"2","key":"451_CR13","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10100-011-0204-9","volume":"21","author":"S Khebbache-Hadji","year":"2013","unstructured":"Khebbache-Hadji S, Prins C, Yalaoui A et al (2013) Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. CEJOR 21(2):307\u2013336","journal-title":"CEJOR"},{"issue":"8","key":"451_CR14","doi-asserted-by":"publisher","first-page":"1795","DOI":"10.1016\/j.engappai.2013.03.012","volume":"26","author":"P Lacomme","year":"2013","unstructured":"Lacomme P, Toussaint H, Duhamel C (2013) A GRASP$$\\times $$ELS for the vehicle routing problem with basic three-dimensional loading constraints. Eng Appl Artif Intell 26(8):1795\u20131810","journal-title":"Eng Appl Artif Intell"},{"key":"451_CR15","doi-asserted-by":"crossref","unstructured":"Li X, Yuan M, Chen D et\u00a0al (2018) A data-driven three-layer algorithm for split delivery vehicle routing problem with 3D container loading constraint. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp 528\u2013536","DOI":"10.1145\/3219819.3219872"},{"key":"451_CR16","doi-asserted-by":"publisher","unstructured":"Liu F, Zhang Q, Zhu Q et al (2024) Machine learning assisted multiobjective evolutionary algorithm for routing and packing. IEEE Trans Evolut Comput Early Access. https:\/\/doi.org\/10.1109\/TEVC.2024.3357819","DOI":"10.1109\/TEVC.2024.3357819"},{"key":"451_CR17","doi-asserted-by":"publisher","first-page":"100927","DOI":"10.1016\/j.swevo.2021.100927","volume":"66","author":"S Liu","year":"2021","unstructured":"Liu S, Tang K, Yao X (2021) Memetic search for vehicle routing with simultaneous pickup-delivery and time windows. Swarm Evol Comput 66:100927. https:\/\/doi.org\/10.1016\/j.swevo.2021.100927","journal-title":"Swarm Evol Comput"},{"key":"451_CR18","doi-asserted-by":"publisher","unstructured":"Lu X, Tang K, Menzel S et\u00a0al (2020) A competitive co-evolutionary optimization method for the dynamic vehicle routing problem. In: 2020 IEEE symposium series on computational intelligence (SSCI), pp 305\u2013312, https:\/\/doi.org\/10.1109\/SSCI47803.2020.9308367","DOI":"10.1109\/SSCI47803.2020.9308367"},{"key":"451_CR19","doi-asserted-by":"crossref","unstructured":"Moura A (2008) A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Intelligent decision support. Springer, p 187\u2013201","DOI":"10.1007\/978-3-8349-9777-7_11"},{"issue":"4","key":"451_CR20","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1007\/s00291-008-0129-4","volume":"31","author":"A Moura","year":"2009","unstructured":"Moura A, Oliveira JF (2009) An integrated approach to the vehicle routing and container loading problems. OR Spectrum 31(4):775\u2013800","journal-title":"OR Spectrum"},{"key":"451_CR21","doi-asserted-by":"crossref","unstructured":"Pei J, Hu C, Liu J et\u00a0al (2021) Bi-objective splitting delivery VRP with loading constraints and restricted access. In: 2021 IEEE symposium series on computational intelligence (SSCI), IEEE, pp 01\u201309","DOI":"10.1109\/SSCI50451.2021.9659967"},{"key":"451_CR22","first-page":"562","volume-title":"PRICAI 2022: Trends in artificial intelligence","author":"J Pei","year":"2022","unstructured":"Pei J, Mei Y, Liu J et al (2022) An investigation of adaptive operator selection in solving complex vehicle routing problem. In: Khanna S, Cao J, Bai Q et al (eds) PRICAI 2022: Trends in artificial intelligence. Springer Nature Switzerland, Cham, pp 562\u2013573"},{"issue":"12","key":"451_CR23","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1016\/S0305-0548(03)00158-8","volume":"31","author":"C Prins","year":"2004","unstructured":"Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Operat Res 31(12):1985\u20132002","journal-title":"Comput Operat Res"},{"key":"451_CR24","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.trc.2014.01.011","volume":"40","author":"C Prins","year":"2014","unstructured":"Prins C, Lacomme P, Prodhon C (2014) Order-first split-second methods for vehicle routing problems: A review. Transp Res Part C Emerging Technol 40:179\u2013200","journal-title":"Transp Res Part C Emerging Technol"},{"issue":"2","key":"451_CR25","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1016\/j.ejor.2021.08.025","volume":"299","author":"M Rajaei","year":"2022","unstructured":"Rajaei M, Moslehi G, Reisi-Nafchi M (2022) The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale. Eur J Oper Res 299(2):706\u2013721. https:\/\/doi.org\/10.1016\/j.ejor.2021.08.025","journal-title":"Eur J Oper Res"},{"issue":"3","key":"451_CR26","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1016\/j.ejor.2017.10.029","volume":"266","author":"S Reil","year":"2018","unstructured":"Reil S, Bortfeldt A, M\u00f6nch L (2018) Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints. Eur J Oper Res 266(3):877\u2013894","journal-title":"Eur J Oper Res"},{"issue":"3","key":"451_CR27","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0954-1810(01)00005-X","volume":"15","author":"KC Tan","year":"2001","unstructured":"Tan KC, Lee LH, Zhu Q et al (2001) Heuristic methods for vehicle routing problem with time windows. Artif Intell Eng 15(3):281\u2013295","journal-title":"Artif Intell Eng"},{"key":"451_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-319-99253-2_8","volume-title":"Parallel problem solving from nature\u2014PPSN XV","author":"R Tin\u00f3s","year":"2018","unstructured":"Tin\u00f3s R, Helsgaun K, Whitley D (2018) Efficient recombination in the Lin\u2013Kernighan\u2013Helsgaun traveling salesman heuristic. In: Auger A, Fonseca CM, Louren\u00e7o N et al (eds) Parallel problem solving from nature\u2014PPSN XV. Springer International Publishing, Cham, pp 95\u2013107"},{"key":"451_CR29","doi-asserted-by":"crossref","unstructured":"Turky A, Moser I, Aleti A (2017) An iterated local search with guided perturbation for the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints. In: Australasian conference on artificial life and computational intelligence, Springer, pp 279\u2013290","DOI":"10.1007\/978-3-319-51691-2_24"},{"key":"451_CR30","doi-asserted-by":"crossref","unstructured":"Wei L, Zhang Z, Lim A (2014) An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints. IEEE Comput Intell Mag 9(4):18\u201330","DOI":"10.1109\/MCI.2014.2350933"},{"key":"451_CR31","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-319-55702-1_47","volume-title":"Operations research proceedings 2016","author":"J Yi","year":"2018","unstructured":"Yi J, Bortfeldt A (2018) The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery\u2013a case study. In: Fink A, F\u00fcgenschuh A, Geiger MJ (eds) Operations research proceedings 2016. Springer International Publishing, Cham, pp 351\u2013356"},{"key":"451_CR32","doi-asserted-by":"crossref","unstructured":"Zhang Z, Wei L, Lim A (2015) An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. Transp Res Part B Methodol 82:20\u201335","DOI":"10.1016\/j.trb.2015.10.001"}],"container-title":["Memetic Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-025-00451-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12293-025-00451-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-025-00451-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T09:30:42Z","timestamp":1750930242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12293-025-00451-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["451"],"URL":"https:\/\/doi.org\/10.1007\/s12293-025-00451-9","relation":{},"ISSN":["1865-9284","1865-9292"],"issn-type":[{"value":"1865-9284","type":"print"},{"value":"1865-9292","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,17]]},"assertion":[{"value":"10 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"18"}}