A New Family of Route Formulations for Split Delivery Vehicle Routing Problems

References

• Alvarez A, Munari P (2022) Heuristic approaches for split delivery vehicle routing problems. Technical report 8790, Operations Research Group, Production Engineering Department, Federal University of Sao Carlos, Sao Carlos, Brazil.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, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45:285–298.Link, Google Scholar
• Archetti C, Savelsbergh MWP, Speranza MG (2006) Worst-case analysis for split delivery vehicle routing problems. Transportation Sci. 40:226–234.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:351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Bektaş T, Laporte G (2011) The pollution-routing problem. Transportation Res. Part B: Methodological 45:1232–1250.Crossref, Google Scholar
• Belfiore P, Yoshizaki HTY (2009) Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. Eur. J. Oper. Res. 199(3):750–758.Crossref, Google Scholar
• Bianchessi N, Irnich S (2019) Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Sci. 53: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:1067–1084.Link, Google Scholar
• Braekers K, Ramaekers K, Nieuwenhuyse IV (2016) The vehicle routing problem: State of the art classification and review. Comput. Industrial Engrg. 99:300–313.Crossref, Google Scholar
• Bulhões T, Pessoa A, Protti F, Uchoa E (2018) On the complete set packing and set partitioning polytopes: Properties and rank 1 facets. Oper. Res. Lett. 46(4):389–392.Crossref, Google Scholar
• Casazza M, Ceselli A, Wolfler Calvo R (2021) A route decomposition approach for the single commodity split pickup and split delivery vehicle routing problem. Eur. J. Oper. Res. 289(3):897–911.Crossref, Google Scholar
• Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58:179–192.Link, Google Scholar
• Desrochers M, Soumis F (1989) A column generation approach to the urban transit crew scheduling problem. Transportation Sci. 23:1–13.Link, Google Scholar
• Dror M, Trudeau P (1989) Savings by split delivery routing. Transportation Sci. 23:141–145.Link, Google Scholar
• Dror M, Trudeau P (1990) Split delivery routing. Naval Res. Logist. 37:383–402.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2006) Vehicle routing with time windows and split deliveries. Technical report, Laboratoire d′Informatique d′Avignon, Université d′Avignon, Avignon, France.Google Scholar
• Frizzell PW, Giffin JW (1995) The split delivery vehicle scheduling problem with time windows and grid network distances. Comput. Oper. Res. 22(6):655–667.Crossref, 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:512–530.Link, Google Scholar
• Ho SC, Haugland D (2004) A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Comput. Oper. Res. 31(12):1947–1964.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Jin M, Liu K, Eksioglu B (2008) A column generation approach for the split delivery vehicle routing problem. Oper. Res. Lett. 36(2):265–270.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
• Li J, Qin H, Baldacci R, Zhu W (2020) Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows. Transportation Res. Part E Logist. Transporation Rev. 140:101955.Crossref, Google Scholar
• Luo Z, Qin H, Zhu W, Lim A (2017) Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transportation Sci. 51:668–687.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: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
• Mullaseril P, Dror M (1996) A set covering approach for directed node and arc routing problems with split deliveries and time windows. Technical report, MIS Department, University of Arizona, Tucson.Google Scholar
• Mullaseril PA, Dror M, Leung J (1997) Split-delivery routing heuristics in livestock feed distribution. J. Oper. Res. Soc. 48(2):107–116.Crossref, Google Scholar
• Munari P, Savelsbergh M (2020) A column generation-based heuristic for the split delivery vehicle routing problem with time windows. SN Oper. Res. Forum 1(4):1–24.Crossref, Google Scholar
• Munari P, Savelsbergh M (2022) Compact formulations for split delivery routing problems. Transportation Sci. 56:1022–1043.Link, 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:85–115.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017a) Improved branch-cut-and-price for capacitated vehicle routing. Math. Program. Comput. 9(1):61–100.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Program. 183:483–523.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017b) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3):206–209.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling, 269–280.Google Scholar
• Sadykov R, Vanderbeck F (2021) BaPCod—A generic branch-and-price code. Technical report HAL-03340548, Inria Bordeaux—Sud-Ouest, Talence, France.Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Shapiro JF (2007) Modeling the Supply Chain, vol. 2 (Thomson Brooks/Cole).Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods and Applications, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Weil A (1983) Number Theory: An Approach Through History. From Hammurapi to Legendre (Birkhäuser, Boston).Google Scholar