{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T13:51:50Z","timestamp":1768312310766,"version":"3.49.0"},"reference-count":37,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:00:00Z","timestamp":1725580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ONR","award":["N00014-17-1-2622"],"award-info":[{"award-number":["N00014-17-1-2622"]}]},{"name":"Lockheed Martin Chair in Systems Engineering","award":["N00014-17-1-2622"],"award-info":[{"award-number":["N00014-17-1-2622"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The split delivery vehicle routing problem (SDVRP) is a relaxed variant of the capacitated vehicle routing problem (CVRP) where the restriction that each customer is visited precisely once is removed. Compared with CVRP, the SDVRP allows a reduction in the total cost of the routes traveled by vehicles. The exact methods to solve the SDVRP are computationally expensive. Moreover, the complexity and difficult implementation of the state-of-the-art heuristic approaches hinder their application in real-life scenarios of the SDVRP. In this paper, we propose an easily understandable and effective approach to solve the SDVPR based on an a priori adaptive splitting algorithm (AASA) that improves the existing state of the art on a priori split strategy in terms of both solution accuracy and time complexity. In this approach, the demand of the customers is split into smaller demand values using a splitting rule in advance. Consequently, the original SDVRP instance is converted to a CVRP instance which is solved using an existing CVRP solver. While the proposed a priori splitting rule in the literature is fixed for all customers regardless of their demand and location, we suggest an adaptive splitting rule that takes into account the distance of the customers to the depot and their demand values. Our experiments show that AASA can generate solutions comparable to the state of the art, but much faster.<\/jats:p>","DOI":"10.3390\/a17090396","type":"journal-article","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:22:46Z","timestamp":1725592966000},"page":"396","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["AASA: A Priori Adaptive Splitting Algorithm for the Split Delivery Vehicle Routing Problem"],"prefix":"10.3390","volume":"17","author":[{"given":"Nariman","family":"Torkzaban","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anousheh","family":"Gholami","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John S.","family":"Baras","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5270-6094","authenticated-orcid":false,"given":"Bruce L.","family":"Golden","sequence":"additional","affiliation":[{"name":"Robert H. Smith School of Business, University of Maryland, College Park 20742, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,9,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1287\/trsc.23.2.141","article-title":"Savings by split delivery routing","volume":"23","author":"Dror","year":"1989","journal-title":"Transp. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1287\/trsc.1050.0117","article-title":"Worst-case analysis for split delivery vehicle routing problems","volume":"40","author":"Archetti","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1057\/palgrave.jors.2600338","article-title":"Split-delivery routing heuristics in livestock feed distribution","volume":"48","author":"Mullaseril","year":"1997","journal-title":"J. Oper. Res. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1023\/A:1018900705946","article-title":"Routing helicopters for crew exchanges on off-shore locations","volume":"76","author":"Sierksma","year":"1998","journal-title":"Ann. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0360-8352(02)00077-3","article-title":"A practical approach to solving a newspaper logistics problem using a digital map","volume":"43","author":"Song","year":"2002","journal-title":"Comput. Ind. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/j.apm.2023.11.009","article-title":"A multi-day waste collection and transportation problem with selective collection and split delivery","volume":"126","author":"Luo","year":"2024","journal-title":"Appl. Math. Model."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1016\/j.trc.2009.12.006","article-title":"Complexity of the VRP and SDVRP","volume":"19","author":"Archetti","year":"2011","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1002\/net.20467","article-title":"A column generation approach for the split delivery vehicle routing problem","volume":"58","author":"Archetti","year":"2011","journal-title":"Networks"},{"key":"ref_9","first-page":"467","article-title":"A Branch-and-cut algorithm for the split-demand one-commodity pickup-anddelivery travelling salesman problem","volume":"297","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1016\/j.ejor.2020.07.032","article-title":"The pickup and delivery problem with split loads and transshipments: A branch-and-cut solution approach","volume":"289","author":"Wolfinger","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1016\/j.ejor.2019.07.015","article-title":"A route decomposition approach for the single commodity Split Pickup and Split Delivery Vehicle Routing Problem","volume":"289","author":"Casazza","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"108137","DOI":"10.1016\/j.cie.2022.108137","article-title":"Exact algorithms for the multiple depot vehicle scheduling problem with heterogeneous vehicles, split loads and toll-by-weight scheme","volume":"168","author":"Li","year":"2022","journal-title":"Comput. Ind. Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"101955","DOI":"10.1016\/j.tre.2020.101955","article-title":"Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows","volume":"140","author":"Li","year":"2020","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.ejor.2019.04.008","article-title":"Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem","volume":"278","author":"Gschwind","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","first-page":"125","article-title":"Maximum-minimum distance clustering method for split-delivery vehicle-routing problem: Case studies and performance comparisons","volume":"14","author":"Min","year":"2019","journal-title":"Adv. Prod. Eng. Manag."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.cie.2017.07.031","article-title":"Two-layer simulated annealing and tabu search heuristics for a vehicle routing problem with cross docks and split deliveries","volume":"112","author":"Wang","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s11277-018-5464-4","article-title":"An adaptive tabu search algorithm for the open vehicle routing problem with split deliveries by order","volume":"103","author":"Xia","year":"2018","journal-title":"Wirel. Pers. Commun."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Xia, Y., Fu, Z., Tsai, S.B., and Wang, J. (2018). A new TS algorithm for solving low-carbon logistics vehicle routing problem with split deliveries by backpack\u2014From a green operation perspective. Int. J. Environ. Res. Public Health, 15.","DOI":"10.3390\/ijerph15050949"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ma, X., and Liu, C. (2024). Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem. Appl. Sci., 14.","DOI":"10.3390\/app14125090"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"110336","DOI":"10.1109\/ACCESS.2020.3001590","article-title":"Goods consumed during transit in split delivery vehicle routing problems: Modeling and solution","volume":"8","author":"Yang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_21","first-page":"196","article-title":"Integrated multi-item packaging and vehicle routing with split delivery problem for fresh agri-product emergency supply at large-scale epidemic disease context","volume":"8","author":"Jiang","year":"2020","journal-title":"J. Traffic Transp. Eng. (Engl. Ed.)"},{"key":"ref_22","first-page":"1521","article-title":"Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up","volume":"41","author":"Fan","year":"2021","journal-title":"Syst. Eng.-Theory Pract."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1840006","DOI":"10.1142\/S0217595918400067","article-title":"Particle swarm optimization for split delivery vehicle routing problem","volume":"35","author":"Shi","year":"2018","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_24","first-page":"1397","article-title":"Split vehicle route planning with full load demand based on particle swarm optimization","volume":"36","author":"Qing","year":"2021","journal-title":"J. Control Decis."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.orl.2007.05.012","article-title":"A column generation approach for the split delivery vehicle routing problem","volume":"36","author":"Jin","year":"2008","journal-title":"Oper. Res. Lett."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1287\/trsc.2018.0862","article-title":"The split delivery vehicle routing problem with time windows and customer inconvenience constraints","volume":"53","author":"Bianchessi","year":"2019","journal-title":"Transp. Sci."},{"key":"ref_27","unstructured":"Alvarez, A., and Munari, P. (2023, August 31). A Matheuristic Approach for Split Delivery Vehicle Routing Problems. Available online: http:\/\/www.optimization-online.org\/DB_FILE\/2022\/02\/8790.pdf."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"105643","DOI":"10.1016\/j.cor.2021.105643","article-title":"Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood","volume":"140","author":"Vidal","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1287\/trsc.2021.1106","article-title":"Compact formulations for split delivery routing problems","volume":"56","author":"Munari","year":"2022","journal-title":"Transp. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1111\/itor.12250","article-title":"A novel approach to solve the split delivery vehicle routing problem","volume":"24","author":"Chen","year":"2017","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1016\/j.ejor.2011.03.023","article-title":"Branch and price for the vehicle routing problem with discrete split deliveries and time windows","volume":"213","author":"Salani","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","unstructured":"Groer, C. (2024, August 01). VRPH. Available online: https:\/\/github.com\/coin-or\/VRPH."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/trsc.1070.0204","article-title":"An optimization-based heuristic for the split delivery vehicle routing problem","volume":"42","author":"Archetti","year":"2008","journal-title":"Transp. Sci."},{"key":"ref_34","first-page":"318","article-title":"The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results","volume":"49","author":"Chen","year":"2007","journal-title":"Netw. Int. J."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s12532-010-0013-5","article-title":"A Library of Local Search Heuristics for the Vehicle Routing Problem","volume":"2","author":"Groer","year":"2010","journal-title":"Math. Program. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1287\/opre.48.5.801.12407","article-title":"A lower bound for the split delivery vehicle routing problem","volume":"48","author":"Belenguer","year":"2000","journal-title":"Oper. Res."},{"key":"ref_37","unstructured":"Reinhelt, G. (2023, August 31). TSPLIB: A Library of Sample Instances for the TSP (and Related Problems) from Various Sources and of Various Types. Available online: http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/9\/396\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:49:34Z","timestamp":1760111374000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/9\/396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,6]]},"references-count":37,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["a17090396"],"URL":"https:\/\/doi.org\/10.3390\/a17090396","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,6]]}}}