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

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 learning-based enhancement for the cutting-edge three-phase branching strategy for column-generation-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 time-consuming 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 2LBB-dy, achieves a 47% time reduction compared with the SOTA VRPSolver for the CVRP.

Funding: This work was supported by the National Science Foundation [Grant CMMI-2309667] and the Alibaba Group US [Grant AGR00022274].

Supplemental Material: This article includes an online appendix, computer code and data supporting the study’s findings, and replication files. All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2023.0615.

Supplemental Review: The empirical results in this paper were replicated. The code, data, and files required to reproduce the results were reviewed and are available at https://doi.org/10.1287/opre.2023.0615.