Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Agra A, Christiansen M, Delgado A (2013) Mixed integer formulations for a short sea fuel oil distribution problem. Transportation Sci. 47(1):108–124.Link, 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
• 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
• 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
• Bode C, Irnich S (2014) The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem. Eur. J. Oper. Res. 238(2):415–426.Crossref, Google Scholar
• Bulhões T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93:66–78.Crossref, Google Scholar
• Cherkesly M, Gschwind T (2022) The pickup and delivery problem with time windows, multiple stacks, and handling operations. Eur. J. Oper. Res. 301(2):647–666.Crossref, Google Scholar
• Cherkesly M, Desaulniers G, Irnich S, Laporte G (2016) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks. Eur. J. Oper. Res. 250(3):782–793.Crossref, Google Scholar
• Christiansen M, Fagerholt K, Flatberg T, Haugen Ø, Kloster O, Lund EH (2011) Maritime inventory routing with multiple products: A case study from the cement industry. Eur. J. Oper. Res. 208(1):86–94.Crossref, Google Scholar
• Coelho LC, Laporte G (2015) Classification, models and exact algorithms for multi-compartment delivery problems. Eur. J. Oper. Res. 242(3):854–864.Crossref, Google Scholar
• Cornillier F, Boctor FF, Laporte G, Renaud J (2008) An exact algorithm for the petrol station replenishment problem. J. Oper. Res. Soc. 59(5):607–615.Crossref, Google Scholar
• Correia I, Gouveia L, Saldanha-da Gama F (2008) Solving the variable size bin packing problem with discretized formulations. Comput. Oper. Res. 35(6):2103–2113.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
• Dantzig G, Ramser J (1959) The truck dispatching problem. Management Sci. 6:80–91.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
• Desaulniers G, Villeneuve D (2000) The shortest path problem with time windows and linear waiting costs. Transportation Sci. 34(3):312–319.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon M, eds. (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Desaulniers G, Rakke JG, Coelho LC (2016b) A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Sci. 50(3):1060–1076.Link, Google Scholar
• Desaulniers G, Errico F, Irnich S, Schneider M (2016a) Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6):1388–1405.Link, Google Scholar
• Desaulniers G, Desrosiers J, Ioachim IM, Solomon M, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Crainic TG, Laporte G, eds. Fleet Management and Logistics (Springer, Berlin), 57–93.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Drexl M (2007) On some generalized routing problems. PhD dissertation, Faculty of Business and Economics, RWTH Aachen University, Aachen, Germany.Google Scholar
• Drexl M (2012) Rich vehicle routing in theory and practice. Logist. Res. 5(1–2):47–63.Crossref, Google Scholar
• Gamache M, Soumis F, Marquis G, Desrosiers J (1999) A column generation approach for large-scale aircrew rostering problems. Oper. Res. 47(2):247–263.Link, Google Scholar
• Goeke D, Gschwind T, Schneider M (2019) Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier. Discrete Appl. Math. 264:43–61.Crossref, Google Scholar
• Gschwind T, Irnich S (2015) Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Sci. 49(2):335–354.Link, Google Scholar
• Gschwind T, Bianchessi N, Irnich S (2019) Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem. Eur. J. Oper. Res. 278(1):91–104.Crossref, Google Scholar
• He Q, Irnich S, Song Y (2019) Branch-and-cut-and-price for the vehicle routing problem with time windows and convex node costs. Transportation Sci. 53(5):1409–1426.Link, Google Scholar
• Henke T, Speranza MG, Wäscher G (2015) The multi-compartment vehicle routing problem with flexible compartment sizes. Eur. J. Oper. Res. 246(3):730–743.Crossref, Google Scholar
• Heßler K (2021) Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes. Eur. J. Oper. Res. 294(1):188–205.Crossref, Google Scholar
• Heßler K, Irnich S, Kreiter T, Pferschy U (2021) Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system. OR Spectrum 44(2):1–43.Crossref, Google Scholar
• Houck D, Picard J, Queyranne M, Vemuganti R (1980) The travelling salesman problem as a constrained shortest path problem: Theory and computational experience. Opsearch 17:93–109.Google Scholar
• Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999) Fleet assignment and routing with schedule synchronization constraints. Eur. J. Oper. Res. 119(1):75–90.Crossref, Google Scholar
• Ioachim I, Gélinas S, Desrosiers J, Soumis F (1998) A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31:193–204.Crossref, Google Scholar
• Irnich S (2008) Resource extension functions: Properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148.Crossref, 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, Toth P, Vigo D (2014) The family of vehicle routing problems. Vigo D, Toth P, eds. Vehicle Routing (SIAM, Philadelphia), 1–33.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
• Kiilerich L, Wøhlk S (2017) New large-scale data instances for CARP and new variations of CARP. INFOR Inform. Systems Oper. Res. 56(1):1–32.Google Scholar
• Kohl N, Desrosiers J, Madsen O, Solomon M, Soumis F (1999) 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Lahyani R, Coelho LC, Khemakhem M, Laporte G, Semet F (2015) A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia. Omega 51:1–10.Crossref, Google Scholar
• Liberatore F, Righini G, Salani M (2010) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1):49–82.Crossref, Google Scholar
• Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Oppen J, Løkketangen A (2008) A tabu search approach for the livestock collection problem. Comput. Oper. Res. 35(10):3213–3229.Crossref, Google Scholar
• Ostermeier M, Henke T, Hübner A, Wäscher G (2021) Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. Eur. J. Oper. Res. 292(3):799–817.Crossref, Google Scholar
• Ostermeier M, Martins S, Amorim P, Hübner A (2018) Loading constraints for a multi-compartment vehicle routing problem. OR Spectrum. 40(4):997–1027.Crossref, Google Scholar
• Parragh SN, Cordeau JF (2017) Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Comput. Oper. Res. 83:28–44.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Ralphs T, Kopman L, Pulleyblank W, Trotter L (2003) On the capacitated vehicle routing problem. Math. Programming 94(2–3):343–359.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
• Rothenbächer AK, Drexl M, Irnich S (2018) Branch-and-price-and-cut for the truck-and-trailer routing problem with time windows. Transportation Sci. 52(5):1174–1190.Link, Google Scholar
• Spliet R, Gabor AF (2015) The time window assignment vehicle routing problem. Transportation Sci. 49(4):721–731.Link, Google Scholar
• Tilk C, Rothenbächer AK, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• Tilk C, Bianchessi N, Drexl M, Irnich S, Meisel F (2018) Branch-and-price-and-cut for the active-passive vehicle-routing problem. Transportation Sci. 52(2):300–319.Link, Google Scholar