Two-Stage Learning to Branch in Branch-Price-and-Cut Algorithms for Solving Vehicle Routing Problems Exactly
提出首个针对分支定价切割算法的两阶段学习分支策略，通过廉价特征筛选和部分测试减少昂贵计算，在标准算例上实现45%-50%的运行时间缩减，并集成到开源求解器RouteOpt中加速47%。
Smarter Branching Speeds Up Leading Exact Vehicle Routing Solvers Researchers have introduced a learning-based branching strategy that substantially accelerates exact algorithms for vehicle routing problems, a core challenge in logistics and transportation systems. The study proposes the first learning-to-branch framework tailored for branch-price-and-cut methods, where dynamic variables and dense constraints make traditional branching decisions computationally expensive. The novel two-stage learning-based branching (2LBB) approach effectively filters promising candidates using inexpensive features and then applies selective, partial testing to reduce costly evaluations. A theoretical model further guides dynamic adjustment of branching effort, balancing decision time with solution quality. Extensive experiments show runtime reductions of 45%–50% on standard CVRP and VRPTW benchmarks and a 47% speedup over the state-of-the-art VRPSolver when integrated into the open-source RouteOpt. These results highlight the growing potential of disciplined machine learning to enhance exact optimization algorithms.