Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem

We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, i.e., a problem consisting of clustering customers into groups, routing a vehicle for each group, and packing demands of the visited customer uniquely into one of the vehicle’s compartments. Compartments have a fixed size, and there are no incompatibilities between the transported items or between items and compartments. The objective is to minimize the total distance of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when exactly solving the problem with a branch-price-andcut algorithm. For this subproblem, we compare a standard dynamic-programming labeling approach with a new one that utilizes a partial dominance. While the algorithm with standard labeling already struggles with relatively small instances, the one with partial dominance can cope with much larger instances.