Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries

References

• Akiba T, Sano S, Yanase T, Ohta T, Koyama M (2019) Optuna: A next-generation hyperparameter optimization framework. Proc. 25th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining KDD ‘19 (Association for Computing Machinery, New York), 2623–2631.Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks 58(4):241–254.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2014) Branch-and-cut algorithms for the split delivery vehicle routing problem. Eur. J. Oper. Res. 238(3):685–698.Crossref, Google Scholar
• Archetti C, Mansini R, Speranza MG (2005) Complexity and reducibility of the skip delivery problem. Transportation Sci. 39(2):182–187.Link, Google Scholar
• Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transportation Sci. 40(1):64–73.Link, Google Scholar
• Archetti C, Speranza MG, Savelsbergh MW (2008) An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Sci. 42(1):22–31.Link, Google Scholar
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, Google Scholar
• Belenguer JM, Martinez MC, Mota E (2000) A lower bound for the split delivery vehicle routing problem. Oper. Res. 48(5):801–810.Link, Google Scholar
• Bellmore M, Nemhauser GL (1968) The traveling salesman problem: A survey. Oper. Res. 16(3):538–558.Link, Google Scholar
• Berbotto L, García S, Nogales FJ (2014) A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Ann. Oper. Res. 222(1):153–173.Crossref, Google Scholar
• Boudia M, Prins C, Reghioui M (2007) An effective memetic algorithm with population management for the split delivery vehicle routing problem. Proc. Hybrid Metaheuristics 4th Internat. Workshop HM 2007 (Springer, Berlin, Heidelberg), 16–30.Google Scholar
• Burke EK, Bykov Y (2017) The late acceptance hill-climbing heuristic. Eur. J. Oper. Res. 258(1):70–78.Crossref, Google Scholar
• Chen S, Golden B, Wasil E (2007) The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks 49(4):318–329.Crossref, Google Scholar
• Chen P, Golden B, Wang X, Wasil E (2017) A novel approach to solve the split delivery vehicle routing problem. Internat. Trans. Oper. Res. 24(1–2):27–41.Crossref, Google Scholar
• Christiaens J, Vanden Berghe G (2020) Slack induction by string removals for vehicle routing problems. Transportation Sci. 54(2):417–433.Link, Google Scholar
• Dror M, Trudeau P (1989) Savings by split delivery routing. Transportation Sci. 23(2):141–145.Link, Google Scholar
• Dror M, Trudeau P (1990) Split delivery routing. Naval Res. Logist. 37(3):383–402.Crossref, Google Scholar
• Elshaer R, Awad H (2020) A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Comput. Indust. Engrg. 140:106242.Crossref, Google Scholar
• Floyd RW (1962) Algorithm 97: Shortest path. Commun. ACM 5(6):345.Crossref, Google Scholar
• Gamma E, Helm R, Johnson R, Vlissides J (1995) Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Longman Publishing Co., Inc., Boston).Google Scholar
• Han AFW, Chu YC (2016) A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts. Transportation Res. Part E Logist. Transportation Rev. 88:11–31.Crossref, Google Scholar
• He P, Hao J-K (2023) General edge assembly crossover-driven memetic search for split delivery vehicle routing. Transportation Sci. 57(2):482–511.Link, Google Scholar
• Hemmelmayr VC (2015) Sequential and parallel large neighborhood search algorithms for the periodic location routing problem. Eur. J. Oper. Res. 243(1):52–60.Crossref, Google Scholar
• Jin M, Liu K, Bowden RO (2007) A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. Internat. J. Production Econom. 105(1):228–242.Crossref, Google Scholar
• Konstantakopoulos GD, Gayialis SP, Kechagias EP (2022) Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Oper. Res. 22:2033–2062.Crossref, Google Scholar
• Lee C-G, Epelman MA, White CC III, Bozer YA (2006) A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation Res. Part B Methodological. 40(4):265–284.Crossref, Google Scholar
• Li X, Yuan M, Chen D, Yao J, Zeng J (2018) A data-driven three-layer algorithm for split delivery vehicle routing problem with 3D container loading constraint. Proc. 24th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 528–536.Google Scholar
• Lin W, He Z, Jiang S, Ma F, Su Z, Lü Z (2025) Alkaid-SDVRP: An efficient open-source solver for the vehicle routing problem with split deliveries. http://dx.doi.org/10.1287/ijoc.2024.0606.cd, https://github.com/INFORMSJoC/2024.0606.Google Scholar
• Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Glover F, Kochenberger GA, eds. Handbook of Metaheuristics (Springer US, Boston), 320–353.Crossref, Google Scholar
• Mor A, Speranza MG (2022) Vehicle routing problems over time: A survey. Ann. Oper. Res. 314(1):255–275.Crossref, Google Scholar
• Mota E, Campos V, Corberán Á (2007) A new metaheuristic for the vehicle routing problem with split demands. Proc. 7th Evolutionary Comput. Combinatorial Optim. 7th Eur. Conf. EvoCOP 2007 (Springer, Berlin, Heidelberg), 121–129.Google Scholar
• Penna PHV, Subramanian A, Ochi LS (2013) An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. J. Heuristics 19(2):201–232.Crossref, Google Scholar
• Silva MM, Subramanian A, Ochi LS (2015) An iterated local search heuristic for the split delivery vehicle routing problem. Comput. Oper. Res. 53(1):234–249.Crossref, Google Scholar
• Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Sci. 31(2):170–186.Link, Google Scholar
• Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140(1):105643.Crossref, Google Scholar
• Xing LN, Liu Y, Li H, Wu CC, Lin WC, Song W (2020) A hybrid discrete differential evolution algorithm to solve the split delivery vehicle routing problem. IEEE Access 8:207962–207972.Crossref, Google Scholar
• Zachariadis EE, Kiranoudis CT (2010) A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem. Comput. Oper. Res. 37(12):2089–2105.Crossref, Google Scholar
• Zhang Z, He H, Luo Z, Qin H, Guo S (2015) An efficient forest-based tabu search algorithm for the split-delivery vehicle routing problem. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Austin), 3432–3438.Google Scholar