Abstrct. 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, which gives rise to a novel two-stage learningbased branching (2LBB) strategy. In the 2LBB, the first stage focuses on narrowing down the list of promising candidates using computationally cheap features, while the second stage seeks to identify the best several candidates using additional information that is more time-consuming to collect. Moreover, we propose a novel theoretical model characterizing the fundamental trade-off 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 time-consuming score computation. Through an extensive numerical study, we demonstrate that a dynamic version of the 2LBB, denoted by 2LBB-dy, is around 45% and 50%, respectively, faster than the state-ofthe-art (SOTA) hand-crafted branching strategy in solving the capacitated vehicle routing problem (CVRP) and VRP with time windows (VRPTW). In addition, our Route Opt (an exact VRP solver available at https://github.com/Zhengzhong-You/RouteOpt), when equipped with the 2LBB-dy, is over 45% and 55% faster than the SOTA VRPSolver from Pessoa et al. (2020) for the CVRP and VRPTW, respectively.