Cluster Branching for Vehicle Routing Problems

This article introduces cluster branching, a novel branching strategy for exact algorithms solving vehicle routing problems (VRPs). Whereas branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as edge branching, CutSet branching, and Ryan and 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 capacitated VRPs and VRPs with time windows instances, we demonstrate that cluster branching (CB) 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, CB is also shown to have a robust performance over different instance types and may work well even for those with randomly positioned customers. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research was partially supported by the following Brazilian research agencies: Comissão de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) [Finance Code 001], Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) [Grants 406245/2021-5, 309580/2021-8, and 313601/2018-6], Paraíba State Research Foundation (FAPESQ) [Grant 041/2023], Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ) [Grant E-26/202.887/2017], as well as by Universidade Federal da Paraíba [Public Call No. 03/2020, “Produtividade em Pesquisa PROPESQ/PRPG/UFPB,” proposal code PVL13400-2020]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1036 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1036 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .