Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 13, 2026

Available Issues

April 10, 2013 - May 13, 2026

Multi-Depot Routing with Split Deliveries: Models and a Branch-and-Cut Algorithm

Published Online:14 Oct 2022https://doi.org/10.1287/trsc.2022.1179

References

  • 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, Savelsbergh MW, Speranza MG (2006a) Worst-case analysis for split delivery vehicle routing problems. Transportation Sci. 40(2):226–234.Link, Google Scholar
  • Archetti C, Speranza MG, Hertz A (2006b) A tabu search algorithm for the split delivery vehicle routing problem. Transportation Sci. 40(1):64–73.Link, Google Scholar
  • Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120(2):347–380.Crossref, Google Scholar
  • Bektaş T, Gouveia L, Santos D (2017) New path elimination constraints for multi-depot routing problems. Networks 70(3):246–261.Crossref, Google Scholar
  • Bektaş T, Gouveia L, Santos D (2020) Compact formulations for multi-depot routing problems: Theoretical and computational comparisons. Comput. Oper. Res. 124:105084.Crossref, Google Scholar
  • Belenguer J-M, Benavent E (2003) A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30(5):705–728.Crossref, Google Scholar
  • Belenguer J-M, Martinez M, Mota E (2000) A lower bound for the split delivery vehicle routing problem. Oper. Res. 48(5):801–810.Link, Google Scholar
  • Belenguer J-M, Benavent E, Prins C, Prodhon C, Calvo RW (2011) A branch-and-cut method for the capacitated location-routing problem. Comput. Oper. Res. 38(6):931–941.Crossref, Google Scholar
  • Benavent E, Martínez A (2013) Multi-depot multiple TSP: A polyhedral study and computational results. Ann. Oper. Res. 207(1):7–25.Crossref, Google Scholar
  • Bianchessi N, Irnich S (2019) Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Sci. 53(2):442–462.Link, Google Scholar
  • Bianchessi N, Drexl M, Irnich S (2019) The split delivery vehicle routing problem with time windows and customer inconvenience constraints. Transportation Sci. 53(4):1067–1084.Link, Google Scholar
  • Blasum U, Hochstättler W (2000) Application of the branch and cut method to the vehicle routing problem. Technical report, Zentrum für Angewandte Informatik, Köln.Google Scholar
  • Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182.Link, 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: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
  • Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.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 (NRL).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
  • Fernández E, Roca-Riu M, Speranza MG (2018) The shared customer collaboration vehicle routing problem. Eur. J. Oper. Res. 265(3):1078–1093.Crossref, Google Scholar
  • Grötschel M, Padberg MW (1985) Polyhedral theory. Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, eds. The Traveling Salesman Problem (Wiley, New York), 251–305.Google Scholar
  • Gulczynski D (2010) Integer programming-based heuristics for vehicle routing problems. PhD thesis, Robert H. Smith School of Business, University of Maryland, College Park, MD.Google Scholar
  • Gulczynski D, Golden B, Wasil E (2011) The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Comput. Industry Engrg. 61(3):794–804.Crossref, Google Scholar
  • Hernández-Pérez H, Salazar-González J-J (2019) Optimal solutions for the vehicle routing problem with split demands. Proc. Internat. Conf. on Comput. Logist. (Springer, Berlin), 189–203.Google Scholar
  • Laporte G, Nobert Y, Arpin D (1984) Optimal solutions to capacitated multidepot vehicle routing problems. Congressus Numerantium 44:283–292.Google Scholar
  • Laporte G, Nobert Y, Arpin D (1986) An exact algorithm for solving a capacitated location-routing problem. Ann. Oper. Res. 6:293–310.Crossref, Google Scholar
  • Laporte G, Nobert Y, Taillefer S (1988) Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Sci. 22(3):161–172.Link, Google Scholar
  • Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
  • Moreno L, De Aragao 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 MW (2022) Compact formulations for split delivery routing problems. Transportation Sci. 56(4):1022–1043.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
  • Padberg M, Grötschel M (1985) Polyhedral computations. Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, eds. The Traveling Salesman Problem (Wiley, New York), 307–360.Google Scholar
  • Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Sci. 45(3):364–380.Link, Google Scholar
  • Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183:483–523.Crossref, Google Scholar
  • Ray S, Soeanu A, Berger J, Debbabi M (2014) The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge Base Systems 71:238–265.Crossref, 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
  • 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
  • uit het Broek MAJ, Schrotenboer AH, Jargalsaikhan B, Roodbergen KJ, Coelho LC (2021) Asymmetric multi-depot vehicle routing problems: Valid inequalities and a branch-and-cut algorithm. Oper. Res. 69(2):380–409.Link, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree