A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries

References

• Archetti C, Speranza MG (2008) The split delivery vehicle routing problem: A survey. Golden BL, Raghavan S, Wasil EA, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York), 103–122.Crossref, Google Scholar
• Archetti C, Speranza MG (2012) Vehicle routing problems with split deliveries. Internat. Trans. Oper. Res. 19(1-2):3–22.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2011a) 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 (2011b) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45(3):285–298.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 (2012) Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218(1):1–6.Crossref, Google Scholar
• Balinski ML, Quandt RE (1964) On an integer program for a delivery problem. Oper. Res. 12(2):300–304.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Battarra M, Cordeau J-F, Iori M (2014) Pickup-and-delivery problems for goods transportation. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 161–191.Crossref, Google Scholar
• Berbeglia G, Cordeau J-F, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: A classification scheme and survey. TOP 15(1):1–31.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
• Bruck BP, Cruz F, Iori M, Subramanian A (2019) The static bike sharing rebalancing problem with forbidden temporary operations. Transportation Sci. 53(3):882–896.Link, Google Scholar
• Bulhões T, Subramanian A, Erdoğan G, Laporte G (2018) The static bike relocation problem with multiple vehicles and visits. Eur. J. Oper. Res. 264(2):508–523.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
• Casazza M, Ceselli A, Chemla D, Meunier F, Wolfler Calvo R (2019) The multiple vehicle balancing problem. Networks 72(3):337–357.Crossref, Google Scholar
• Chabrier A (2006) Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. 33(10):2972–2990.Crossref, Google Scholar
• Chemla D, Meunier F, Wolfler Calvo R (2013) Bike sharing systems: Solving the static rebalancing problem. Discrete Optim. 10(2):120–146.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Cruz F, Subramanian A, Bruck BP, Iori M (2017) A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Comput. Oper. Res. 79:19–33.Crossref, Google Scholar
• Dabia S, Ropke S, van Woensel T, De Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• Dell’Amico M, Hadjicostantinou E, Iori M, Novellani S (2014) The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega 45:7–19.Crossref, Google Scholar
• Dell’Amico 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
• 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
• Desaulniers G, Desrosiers J, Solomon MM, eds. (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Dror M, Trudeau P (1989) Savings by split delivery routing. Transportation Sci. 23(2):141–145.Link, Google Scholar
• Erdoğan G, Battarra M, Wolfler Calvo R (2015) An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. Eur. J. Oper. Res. 245(3):667–679.Crossref, Google Scholar
• Erdoğan G, Laporte G, Wolfler Calvo R (2014) The static bicycle relocation problem with demand intervals. Eur. J. Oper. Res. 238(2):451–457.Crossref, Google Scholar
• Espegren HM, Kristianslund J, Andersson H, Fagerholt K (2016) The static bicycle repositioning problem—literature survey and new formulation. Paias A, Ruthmair M, Voß S, eds. Computational Logistics (Springer, Cham, Switzerland), 337–351.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González J (2004a) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145(1):126–139.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González J (2004b) Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Sci. 38(2):245–255.Link, Google Scholar
• Hernández-Pérez H, Salazar-González J (2007) The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms. Networks 50(4):258–272.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González J, Santos-Hernández B (2018) Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem. Comput. Oper. Res. 97:1–17.Crossref, Google Scholar
• IBM CPLEX (2019) IBM ILOG CPLEX 12.6.4 callable library.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• Irnich S, Schneider M, Vigo D (2014) Four variants of the vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 241–271.Crossref, Google Scholar
• Izuno T, Nishi T, Yin S (2012), Column generation for split pickup and delivery vehicle routing problem for crude oil transportation. Proc. ASME/ISCIE 2012 Internat. Sympos. Flexible Automation (St. Louis, Missouri), 397–404.Google Scholar
• Joncour C, Michel S, Sadykov R, Sverdlov D, Vanderbeck F (2010) Column generation based primal heuristics. Electronic Notes Discrete Math. 36:695–702.Crossref, Google Scholar
• Laporte G, Meunier F, Wolfler Calvo R (2015) Shared mobility systems. 4OR 13(4):341–360.Crossref, Google Scholar
• Laporte G, Meunier F, Wolfler Calvo R (2018) Shared mobility systems: An updated survey. Ann. Oper. Res. 271(1):105–126.Crossref, Google Scholar
• Liberatore F, Righini G, Salani M (2011) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1):49–82.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, 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(2):668–687.Link, Google Scholar
• Luo Z, Qin H, Cheng TCE, Wu Q, Lim A (2021) A branch-and-price-and-cut algorithm for the cable-routing problem in solar power plants. INFORMS J. Comput. 33(2):452–476.Abstract, Google Scholar
• Parragh S, Doerner K, Hartl R (2008a) A survey on pickup and delivery problems. Part I: Transportation between customers and depot. J. Betriebswirtschaft 58(1):21–51.Crossref, Google Scholar
• Parragh S, Doerner K, Hartl R (2008b) A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations. J. Betriebswirtschaft. 58(2):81–117.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Poggi M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Math. Programming Rio, Buzios, Brazil, November 9–12, 56–61.Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch and price: The assets of diving methods. INFORMS J. Comput. 31(2):251–267.Link, Google Scholar
• Salazar-González J, Santos-Hernández B (2015) The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transportation Res. Part B Methodological. 75:58–73.Crossref, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia).Crossref, Google Scholar
• Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar