Exact and Heuristic Methods for the Split Delivery Vehicle Routing Problem

References

• Aleman RE, Hill RR (2010) A tabu search with vocabulary building approach for the vehicle routing problem with split demands. Internat. J. Metaheuristics 1(1):55–80.Crossref, Google Scholar
• Aleman RE, Zhang X, Hill RR (2010) An adaptive memory algorithm for the split delivery vehicle routing problem. J. Heuristics 16(3):441–473.Crossref, 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, 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, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Balster I, Bulhões T, Munari P, Pessoa AA, Sadykov R (2023) A new family of route formulations for split delivery vehicle routing problems. Transportation Sci. 57(5):1359–1378.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
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Berbotto L, García S, Nogales FJ (2014) A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals Oper. Res. 222(1):153–173.Crossref, Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Boudia M, Prins C, Reghioui M (2007) An effective memetic algorithm with population management for the split delivery vehicle routing problem. Lecture Notes Comput. Sci. 4771:16–30.Crossref, Google Scholar
• Bräysy O, Gendreau M (2005) Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Sci. 39(1):104–118.Link, Google Scholar
• Campos V, Corberán A, Mota E (2008) A scatter search algorithm for the split delivery vehicle routing problem. Studies Comput. Intelligence 144:137–152.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
• Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4):568–581.Link, Google Scholar
• Dell M, Iori M, Novellani S, Stützle T (2016) A destroy and repair algorithm for the bike sharing rebalancing problem. Comput. Oper. Res. 71:149–162.Crossref, Google Scholar
• Derigs U, Li B, Vogel U (2010) Local search-based metaheuristics for the split delivery vehicle routing problem. J. Oper. Res. Soc. 61(9):1356–1364.Crossref, Google Scholar
• DIMACS (2022) SDVRP test instances. Accessed June 24, 2024, http://dimacs.rutgers.edu/files/2915/8102/8622/SDVRP-instances-description.pdf.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
• Dror M, Laporte G, Trudeau P (1994) Vehicle routing with split deliveries. Discrete Appl. Math. 50(3):239–254.Crossref, Google Scholar
• Dueck G (1993) New optimization heuristics: The great deluge algorithm and the record-to-record travel. J. Comput. Phys. 104(1):86–92.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) Jump: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Gamst M, Lusby R, Ropke S (2022) Exact and heuristic methods for the split delivery vehicle routing problem. Accessed June 24, 2024, https://drive.google.com/file/d/1u2xJvFrp_LifSnwCGeNlJwTKEc_2hOZ5/view?usp=sharing.Google Scholar
• Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Management Sci. 40(10):1276–1290.Link, Google Scholar
• Gendreau M, Dejax P, Feillet D, Gueguen C (2006) Vehicle routing with time windows and split deliveries. Technical Report 2006-851, Laboratoire Informatique d’Avignon, Avignon Cedex 9, France.Google Scholar
• Gouveia L, Leitner M, Ruthmair M (2023) Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm. Transportation Sci. 57(2):512–530.Link, Google Scholar
• He P, Hao JK (2023) General edge assembly crossover-driven memetic search for split delivery vehicle routing. Transportation Sci. 57(2):482–511.Link, Google Scholar
• Hernández-Pérez H, Salazar-González JJ (2019) Optimal solutions for the vehicle routing problem with split demands. Lecture Notes Comput. Sci. 11756:189–203.Crossref, Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5(2):77–85.Crossref, Google Scholar
• Lin W, Zhu H, Jiang S, Ma F, Lu Z (2022) An efficient iterated local search heuristic for the split delivery vehicle routing problem. Accessed June 24, 2024, https://drive.google.com/file/d/1I6gpUTF-z9WNFEsQKc0LZSCjhnXfeMUN.Google Scholar
• Lusby RM, Røpke S, Gamst M, Spoorendonk S (2020) Simultaneously exploiting two formulations: An exact benders decomposition approach. Comput. Oper. Res. 123:105041.Crossref, Google Scholar
• Mejía-de Dios JA, Mezura-Montes E, Quiroz-Castellanos M (2021) Automated parameter tuning as a bilevel optimization problem solved by a surrogate-assisted population-based approach. Appl. Intelligence 51(8):5978–6000.Crossref, Google Scholar
• Moreno L, de Aragão MP, Uchoa E (2010) Improved lower bounds for the split delivery vehicle routing problem. Oper. Res. Lett. 38(4):302–306.Crossref, Google Scholar
• Munari P, Savelsbergh M (2022) Compact formulations for split delivery routing problems. Transportation Sci. 56(4):1022–1043.Link, Google Scholar
• Naddef D, Rinaldi G (2002) Branch-and-cut algorithms for the capacitated VRP. The Vehicle Routing Problem (SIAM, Philadelphia), 53–84.Crossref, Google Scholar
• Ozbaygin G, Karasan O, Yaman H (2018) New exact solution approaches for the split delivery vehicle routing problem. Euro J. Comput. Optim. 6(1):85–115.Crossref, Google Scholar
• Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput. Oper. Res. 34(8):2403–2435.Crossref, Google Scholar
• Pisinger D, Ropke S (2019) Large neighborhood search. Handbook of Metaheuristics (Springer, Berlin), 99–127.Crossref, Google Scholar
• Reinelt G (1991) Tsplib: A traveling salesman problem library. Orsa J. Comput. 3(4):376–384.Link, Google Scholar
• Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. 40(4):455–472.Link, Google Scholar
• Santini A, Ropke S, Hvattum LM (2018) A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. J. Heuristics 24(5):783–815.Crossref, Google Scholar
• Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report, APES Group, Department of Computer Science, University of Strathclyde, Glasgow, Scotland.Google Scholar
• Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. Maher M, Puget JF, eds. Principles and Practice of Constraint Programming — CP98. CP 1998, Lecture Notes in Computer Science, vol. 1520 (Springer, Berlin), 417–431.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:234–249.Crossref, Google Scholar
• Vadseth S, Skålnes J, Andersson H, Stålhane M (2022) Solving the VRP with split deliveries. Accessed June 24, 2024, https://drive.google.com/file/d/1fCvuxoNiR29BMp-KdInAjnHtOjPhBikN/view?usp=sharing.Google Scholar
• Wilck JH IV, Cavalier TM (2012a) A construction heuristic for the split delivery vehicle routing problem. Amer. J. Oper. Res. 02(02):153–162.Google Scholar
• Wilck JH IV, Cavalier TM (2012b) A genetic algorithm for the split delivery vehicle routing problem. Amer. J. Oper. Res. 02(02):207–216.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. Bonet B, Koenig S, eds. Proc. Twenty-Ninth AAAI Conf. Artificial Intelligence, vol. 29 (AAAI Press, Palo Alto, CA), 3432–3438.Google Scholar