This work considers a family of VRP variants that generalizes the classical Capacitated Vehicle Routing Problem by taking into account the existence of a number of vehicle types differ by capacity, costs, depot allocation, or even by the set of customers that they can visit. Those problems are very important in practice, since fleets are likely to be heterogeneous in most real- world situations.

The proposed Branch-Cut-and-Price algorithm combines several state-of-the-art techniques known to be efficient for routing problems : bi-directional ng-path based labeling algorithm to solve the pricing subproblems, generation of limited arc memory rank-1 cuts with up to 5 rows, reduced cost fixing of arc variables, enumeration of elementary routes, automatic dual price smoothing stabilization, and multi-phase strong branching with pseudo-costs.

To improve the master problem relaxation, we additionally generate homogeneous extended capacity cuts. We computationally show that these cuts, even in the presence of rank-1 cuts, are important for solving difficult instances of the problem. Other contributions include pricing subproblem dependent memory for rank-1 cuts, and the concept of « enumerated mode » for pricing subproblems.

The proposed algorithm was tested on a set of standard instances of the problem, including multi-depot and site-dependent variants. The dimension of instances that can solved to optimality was doubled in comparison with the state-of-the-art algorithm by Baldacci and Mingozzi (2009). Several best-known solutions were improved.