Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem

The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a restricted variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, i.e., the streets to be serviced, is partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour problem. Although postman problems with these characteristics have been studied before, there is one fundamental difference here: clusters are not necessarily vertexdisjoint, which prohibits many preprocessing and modeling approaches for clustered postman problems from the literature. We present an undirected and a windy formulation for the pricing subproblem and develop and computationally compare two corresponding branch-and-cut algorithms. Cutting is also performed at the master-program level using subset-row inequalities for subsets of size up to five. For the first time, these non-robust cuts are incorporated into MIP-based routing subproblem solvers using two different modeling approaches. In several computational studies, we calibrate the individual algorithmic components. The final computational experiments prove that the branch-price-and-cut algorithm equipped with these problemtailored components is effective: The largest SoftCluCARP instances solved to optimality have more than 150 required edges or more than 50 clusters.