A branch-and-cut algorithm for the soft-clustered vehicle-routing problem

The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques and a reduction scheme that is also applicable to the respective traveling salesman problem. In comprehensive computational test on standard benchmark instances, we compare the different formulations and separation strategies in order to determine a best performing algorithmic setup. The computational results with this branch-and-cut algorithm show that several previously open instances can now be solved to proven optimality. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem, with a novel symmetric formulation and an asymmetric sub-model for clustering. A branch-and-cut algorithm is used to solve the new model, with problem-specific cutting planes and separation procedures introduced. Computational results show that the algorithm can now solve several previously open instances to proven optimality.