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

• 成果类型: Article
• 署名作者: You, Zhengzhong; Yang, Yu; Wang, Xinshang; Yin, Wotao
• 署名单位: State University System of Florida; University of Florida; State University System of Florida; University of Florida
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0615
• 发表日期: 2026
• 关键词: strategies

摘要

Branching is one of the most important components in branch-price-and-cut (BPC) algorithms for solving vehicle routing problems (VRPs) exactly. However, learning to branch is much more challenging in BPC than in branch-and-cut algorithms that are used for solving general mixed integer programs because branching, in this case, is generally performed by adding a dense constraint to the restricted master problem (RMP), and meanwhile, the variables in the RMP change constantly. To address such challenges, we propose the first effective learning-to-branch framework in BPC algorithms, leading to a novel two-stage learning-based branching (2LBB) strategy. This serves as an innovative learningbased enhancement for the cutting-edge three-phase branching strategy for columngeneration-based algorithms. In the 2LBB, the first stage focuses on narrowing down the list of promising candidates using computationally cheap features thereby lessening dependence on linear programming testing. The second stage, meanwhile, diminishes the burden on heuristic testing through an innovative partial testing approach. Moreover, we propose a novel theoretical model characterizing the fundamental tradeoff between time spent making a single branching decision and the resulting branching quality. A formula, derived from the model, for dynamically adjusting the number of candidates to select for the second stage achieves consistently superior performance to ones obtained from trial-and-error tuning. The derivation easily generalizes to most branching strategies requiring timeconsuming score computation. Through an extensive numerical study, we demonstrate that a dynamic version of the 2LBB, denoted by 2LBB-dy, achieves approximately 45% and 50% time reduction, respectively, compared with the state-of-the-art (SOTA) hand-crafted branching strategy in solving the capacitated vehicle routing problem (CVRP) and vehicle routing problem with time windows. In addition, our RouteOpt (an exact VRP solver available at https://github.com/Zhengzhong-You/RouteOpt), when equipped with the 2LBBdy, achieves a 47% time reduction compared with the SOTA VRPSolver for the CVRP.