Two-Stage Learning to Branch in Branch-Price-and-Cut Algorithms for Solving Vehicle Routing Problems Exactly

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universitat, Berlin.Google Scholar
• Achterberg T, Wunderling R (2013) Mixed integer programming: Analyzing 12 years of progress. Facets of Combinatorial Optimization (Springer, Berlin), 449–481.Crossref, Google Scholar
• Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Applegate D, Bixby R, Chvátal V, Cook W (1995) Finding cuts in the tsp (a preliminary report). Technical report, Center for Research in Parallel Computing, Rice University, Houston.Google Scholar
• Augerat P, Naddef D, Belenguer J, Benavent E, Corberan A, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report No. 949-M, Université Joseph Fourier, Grenoble, France.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
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.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
• Bektaş T, Erdoğan G, Røpke S (2011) Formulations and branch-and-cut algorithms for the generalized vehicle routing problem. Transportation Sci. 45(3):299–316.Link, Google Scholar
• Bénichou M, Gauthier JM, Girodet P, Hentges G, Ribière G, Vincent O (1971) Experiments in mixed-integer linear programming. Math. Programming 1(1):76–94.Crossref, Google Scholar
• Breugem T, Dollevoet T, Huisman D (2022) Is equality always desirable? Analyzing the trade-off between fairness and attractiveness in crew rostering. Management Sci. 68(4):2619–2641.Link, Google Scholar
• Cappart Q, Chételat D, Khalil EB, Lodi A, Morris C, Veličković P (2023) Combinatorial optimization and reasoning with graph neural networks. J. Machine Learn. Res. 24(130):1–61.Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–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
• Costa PR, Rhuggenaath J, Zhang Y, Akcay A (2020) Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. Pan SJ, Sugiyama M, eds. Proc. 12th Asian Conf. Machine Learn. vol. 129 (PMLR, New York), 465–480.Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Desaulniers G, Rakke JG, Coelho LC (2016) A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Sci. 50(3):1060–1076.Link, Google Scholar
• Desrosiers J, Soumis F, Desrochers M (1984) Routing with time windows by column generation. Networks 14(4):545–565.Crossref, Google Scholar
• Engineer FG, Furman KC, Nemhauser GL, Savelsbergh MW, Song JH (2012) A branch-price-and-cut algorithm for single-product maritime inventory routing. Oper. Res. 60(1):106–122.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 15554–15566.Google Scholar
• Gurobi Optimization, LLC (2023) Gurobi optimizer reference manual. Accessed February 13, 2026, https://www.gurobi.com/documentation/10.0/refman/index.html.Google Scholar
• Heching A, Hooker JN, Kimura R (2019) A logic-based benders approach to home healthcare delivery. Transportation Sci. 53(2):510–522.Link, Google Scholar
• Homberger J, Gehring H (2005) A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162(1):220–238.Crossref, Google Scholar
• IBM Corporation (2023) IBM ILOG CPLEX optimization studio CPLEX user’s manual. https://www.ibm.com/docs/en/icos/22.1.0?topic=manuals-cplex-users-manual.Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22(2):297–313.Link, 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
• Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan SVN, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30, (Curran Associates, Inc., Red Hook, NY), 6348–6358.Google Scholar
• Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence 30.Google Scholar
• Laporte G (2009) Fifty years of vehicle routing. Transportation Sci. 43(4):408–416.Link, 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
• Le Bodic P, Nemhauser G (2017) An abstract model for branching and its application to mixed integer programming. Math. Programming 166(1–2):369–405.Crossref, Google Scholar
• Lima I, Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A, et al. (2014) CVRPLIB: Capacitated vehicle routing problem library. http://vrp.galgos.inf.puc-rio.br/index.php/en/updates.Google Scholar
• Linderoth JT, Savelsbergh MW (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2):173–187.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.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
• Mai TL, Navet N (2021) Deep learning to predict the feasibility of priority-based ethernet network configurations. ACM Trans. Cyber-Physical Systems 5(4):1–26.Crossref, Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning–based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Morabit M, Desaulniers G, Lodi A (2022) Machine-learning-based arc selection for constrained shortest path problems in column generation. INFORMS J. Optim. 5(2):191–210.Google Scholar
• Naddef D, Rinaldi G (2002) Branch-and-cut algorithms for the capacitated VRP. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 53–84.Crossref, Google Scholar
• Nazari M, Oroojlooy A, Snyder L, Takác M (2018) Reinforcement learning for solving the vehicle routing problem. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY), 9839–9849.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
• Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017c) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3):206–209.Crossref, Google Scholar
• Pereira P, Courtade E, Aloise D, Quesnel F, Soumis F, Yaakoubi Y (2022) Learning to branch for the crew pairing problem. Les Cahiers du GERAD. Technical Report, GERAD, HEC Montréal.Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Qiu H, Wang D, Yin Y, Cheng TE, Wang Y (2022) An exact solution method for home health care scheduling with synchronized services. Naval Res. Logist. 69(5):715–733.Crossref, Google Scholar
• Quesnel F, Desaulniers G, Soumis F (2020) Improving air crew rostering by considering crew preferences in the crew pairing problem. Transportation Sci. 54(1):97–114.Link, Google Scholar
• Silva JMP, Uchoa E (2024) Cluster branching for vehicle routing problems. INFORMS J. Comput. 36(6):1774–1791.Google Scholar
• Tahir A, Quesnel F, Desaulniers G, El Hallaoui I, Yaakoubi Y (2021) An improved integral column generation algorithm using machine learning for aircrew pairing. Transportation Sci. 55(6):1411–1429.Link, Google Scholar
• Trautsamwieser A, Hirsch P (2014) A branch-price-and-cut approach for solving the medium-term home health care planning problem. Networks 64(3):143–159.Crossref, Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• van der Hagen L, Agatz N, Spliet R, Visser TR, Kok L (2024) Machine learning–based feasibility checks for dynamic time slot management. Transportation Sci. 58(1):94–109.Link, Google Scholar
• Vinsensius A, Wang Y, Chew EP, Lee LH (2020) Dynamic incentive mechanism for delivery slot management in e-commerce attended home delivery. Transportation Sci. 54(3):567–587.Link, Google Scholar
• Yang Y, Boland N, Savelsbergh M (2021) Multivariable branching: A 0-1 knapsack problem case study. INFORMS J. Comput. 33(4):1354–1367.Abstract, Google Scholar
• Yang Y, Boland N, Dilkina B, Savelsbergh M (2022) Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problems. Eur. J. Oper. Res. 301(3):828–840.Crossref, Google Scholar
• Yang Y, Yan C, Cao Y, Roberti R (2023) Planning robust drone-truck delivery routes under road traffic uncertainty. Eur. J. Oper. Res. 309(3):1145–1160.Crossref, Google Scholar
• Zhang X, Chen L, Gendreau M, Langevin A (2022) Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints. INFORMS J. Comput. 34(3):1419–1436.Link, Google Scholar
• Zheng YJ (2018) Emergency train scheduling on Chinese high-speed railways. Transportation Sci. 52(5):1077–1091.Link, Google Scholar