{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:03:30Z","timestamp":1742961810571,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031700545"},{"type":"electronic","value":"9783031700552"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T00:00:00Z","timestamp":1725667200000},"content-version":"vor","delay-in-days":250,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) intertwines complex routing and packing challenges. The current study addresses 3L-SDVRP using intelligent optimization algorithms, which iteratively evolve towards optimal solutions. A pivotal aspect of these algorithms is search operators that determine the search direction and the search step size. Effective operators significantly improve algorithmic performance. Traditional operators like swap, shift, and 2-opt fall short in complex scenarios like 3L-SDVRP, mainly due to their limited capacity to leverage domain knowledge. Additionally, the search step size is crucial: smaller steps enhance fine-grained search (exploitation), while larger steps facilitate exploring new areas (exploration). However, optimally balancing these step sizes remains an unresolved issue in 3L-SDVRP. To address this, we introduce an adaptive knowledge-guided insertion (AKI) operator. This innovative operator uses node distribution characteristics for adaptive node insertion, enhancing search abilities through domain knowledge integration and larger step sizes. Integrating AKI with the local search framework, we develop an adaptive knowledge-guided search (AKS) algorithm, which effectively balances exploitation and exploration by combining traditional neighbourhood operators for detailed searches with the AKI operator for broader exploration. Our experiments demonstrate that the AKS algorithm significantly outperforms the state-of-the-art method in solving various 3L-SDVRP instances.<\/jats:p>","DOI":"10.1007\/978-3-031-70055-2_9","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T19:02:54Z","timestamp":1725649374000},"page":"133-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Knowledge-Guided Optimization for\u00a0Complex Vehicle Routing with\u00a03D Loading Constraints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8243-1135","authenticated-orcid":false,"given":"Han","family":"Zhang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3370-471X","authenticated-orcid":false,"given":"Qing","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8837-4442","authenticated-orcid":false,"given":"Xin","family":"Yao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"issue":"1","key":"9_CR1","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.: A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131(1), 143\u2013161 (2001)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"9_CR2","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.: The split delivery vehicle routing problem with three-dimensional loading constraints. Eur. J. Oper. Res. 282(2), 545\u2013558 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"9_CR3","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.: Local search techniques for a routing-packing problem. Comput. Ind. Eng. 66(4), 1138\u20131149 (2013)","journal-title":"Comput. Ind. Eng."},{"issue":"17","key":"9_CR4","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., Liang, Y., Ding, Y., Wang, L.: The split delivery vehicle routing problem with three-dimensional loading and time windows constraints. Sustainability 12(17), 6987 (2020)","journal-title":"Sustainability"},{"issue":"3","key":"9_CR5","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1287\/ijoc.1070.0250","volume":"20","author":"TG Crainic","year":"2008","unstructured":"Crainic, T.G., Perboli, G., Tadei, R.: Extreme point-based heuristics for three-dimensional bin packing. INFORMS J. Comput. 20(3), 368\u2013384 (2008)","journal-title":"INFORMS J. Comput."},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","volume":"1","author":"K Helsgaun","year":"2009","unstructured":"Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1, 119\u2013163 (2009)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1109\/TEVC.2021.3123960","volume":"26","author":"W Lan","year":"2022","unstructured":"Lan, W., Ye, Z., Ruan, P., Liu, J., Yang, P., Yao, X.: Region-focused memetic algorithms with smart initialization for real-world large-scale waste collection problems. IEEE Trans. Evol. Comput. 26(4), 704\u2013718 (2022). https:\/\/doi.org\/10.1109\/TEVC.2021.3123960","journal-title":"IEEE Trans. Evol. Comput."},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Li, X., Yuan, M., Chen, D., Yao, J., Zeng, J.: 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 (2018)","DOI":"10.1145\/3219819.3219872"},{"key":"9_CR9","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2024.3357819","author":"F Liu","year":"2024","unstructured":"Liu, F., Zhang, Q., Zhu, Q., Tong, X., Yuan, M.: Machine learning assisted multiobjective evolutionary algorithm for routing and packing. IEEE Trans. Evol. Comput. (2024). https:\/\/doi.org\/10.1109\/TEVC.2024.3357819","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"11","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097\u20131100 (1997)","journal-title":"Comput. Oper. Res."},{"key":"9_CR11","unstructured":"Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program, C3P Report, vol. 826, p. 37 (1989)"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-8349-9777-7_11","volume-title":"Intelligent Decision Support","author":"A Moura","year":"2008","unstructured":"Moura, A.: A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Bortfeldt, A., Homberger, J., Kopfer, H., Pankratz, G., Strangmeier, R. (eds.) Intelligent Decision Support, pp. 187\u2013201. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-8349-9777-7_11"},{"issue":"4","key":"9_CR13","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, J.F.: An integrated approach to the vehicle routing and container loading problems. OR Spectrum 31(4), 775\u2013800 (2009)","journal-title":"OR Spectrum"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Pei, J., Hu, C., Liu, J., Mei, Y., Yao, X.: Bi-objective splitting delivery VRP with loading constraints and restricted access. In: 2021 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1\u20139. IEEE (2021)","DOI":"10.1109\/SSCI50451.2021.9659967"},{"issue":"2","key":"9_CR15","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.: The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale. Eur. J. Oper. Res. 299(2), 706\u2013721 (2022). https:\/\/doi.org\/10.1016\/j.ejor.2021.08.025","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"9_CR16","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/trsc.1050.0135","volume":"40","author":"S Ropke","year":"2006","unstructured":"Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40(4), 455\u2013472 (2006)","journal-title":"Transp. Sci."},{"issue":"6","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1579","DOI":"10.1016\/j.cor.2011.11.013","volume":"40","author":"Q Ruan","year":"2013","unstructured":"Ruan, Q., Zhang, Z., Miao, L., Shen, H.: A hybrid approach for the vehicle routing problem with three-dimensional loading constraints. Comput. Oper. Res. 40(6), 1579\u20131589 (2013)","journal-title":"Comput. Oper. Res."},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-49481-2_30","volume-title":"Principles and Practice of Constraint Programming \u2014 CP98","author":"P Shaw","year":"1998","unstructured":"Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417\u2013431. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-49481-2_30"},{"issue":"5","key":"9_CR19","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1109\/TEVC.2009.2023449","volume":"13","author":"K Tang","year":"2009","unstructured":"Tang, K., Mei, Y., Yao, X.: Memetic algorithm with extended neighborhood search for capacitated arc routing problems. IEEE Trans. Evol. Comput. 13(5), 1151\u20131166 (2009)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3\u20134","key":"9_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1080\/00207169108804011","volume":"40","author":"X Yao","year":"1991","unstructured":"Yao, X.: Simulated annealing with extended neighbourhood. Int. J. Comput. Math. 40(3\u20134), 169\u2013189 (1991)","journal-title":"Int. J. Comput. Math."},{"key":"9_CR21","unstructured":"Yao, X.: Dynamic neighbourhood size in simulated annealing. In: Proceedings of International Joint Conference on Neural Networks (IJCNN 1992), vol.\u00a01, pp. 411\u2013416 (1992)"},{"key":"9_CR22","series-title":"Operations Research Proceedings","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.: The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery\u2014a case study. In: Fink, A., F\u00fcgenschuh, A., Geiger, M.J. (eds.) Operations Research Proceedings 2016. ORP, pp. 351\u2013356. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-55702-1_47"},{"key":"9_CR23","doi-asserted-by":"publisher","unstructured":"Zhang, H., Li, Q., Yao, X.: An adaptive interactive routing-packing strategy for split delivery vehicle routing problem with 3d loading constraints. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO 2024. Association for Computing Machinery, New York (2024, in press). https:\/\/doi.org\/10.1145\/3638529.3653991","DOI":"10.1145\/3638529.3653991"},{"key":"9_CR24","doi-asserted-by":"publisher","unstructured":"Zhang, H., Li, Q., Yao, X.: Knowledge-Guided Optimization for Complex Vehicle Routing with 3D Loading Constraints: Supplementary Material (2024). https:\/\/doi.org\/10.5281\/zenodo.10988571","DOI":"10.5281\/zenodo.10988571"},{"issue":"9","key":"9_CR25","doi-asserted-by":"publisher","first-page":"2178","DOI":"10.1016\/j.cor.2011.11.001","volume":"39","author":"W Zhu","year":"2012","unstructured":"Zhu, W., Qin, H., Lim, A., Wang, L.: A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP. Comput. Oper. Res. 39(9), 2178\u20132195 (2012)","journal-title":"Comput. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-70055-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T19:06:05Z","timestamp":1725649565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70055-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700545","9783031700552"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70055-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hagenberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2024.fh-ooe.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}