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

We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, which consists of clustering customers into groups, routing a vehi-cle for each group, and packing the demand of each visited customer 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 mini-mize the total length of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when solving the problem with a branch-price-and-cut algorithm exactly. For this subproblem, we compare a standard dynamic-programming label-ing approach with a new one that uses a partial dominance. The algorithm with standard labeling already struggles with relatively small instances, whereas the one with partial domi-nance can cope with much larger instances.

Automated summary

This study considers the exact solution to the basic version of the multiple-compartment vehicle-routing problem. It focuses on clustering customers, routing vehicles, and packing customer demand into compartments. The objective is to minimize the total length of all vehicle routes. The study compares different labeling approaches for solving the shortest-path subproblem, finding that partial dominance performs better than standard labeling.