This article introduces Cluster Branching, a novel branching strategy for exact algorithms solving Vehicle Routing Problems (VRPs). While branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as Edge Branching, CutSet Branching, and Ryan&Foster Branching have their limitations. The proposed branching strategy aggregates multiple edge variables into higher-level decision structures corresponding to clusters of customers. Through extensive computational experiments on Distance-Constrained VRP, Capacitated VRP, and VRP with Time Windows instances, we demonstrate that Cluster Branching significantly enhances the performance of a state-of-the-art Branch-Cut-and-Price algorithm, often improving branching quality and reducing the size of the search trees, which allows more instances to be solved. Beyond that, Cluster Branching is also shown to have a robust performance over different instance types, and may work well even for those with randomly positioned customers.
Citation
The final version of this work has been published in the INFORMS Journal on Computing, available at: https://doi.org/10.1287/ijoc.2024.1036.