Scientific Program > Talks by Speaker > Hoogendoorn Ymro

We present new valid inequalities for the capacitated vehicle routing problem (CVRP), called the ng-capacity cuts (ng-CCs). These valid inequalities are stronger than the rounded capacity cuts, but still have the attractive property that they are robust when the ng-route relaxation is used in a branch-price-and-cut (BPC) algorithm. That is, including the duals of the ng-CCs in the pricing problem, a shortest path problem with resource constraints, does not require extra resources.
In this paper, we formalize the concept of ng-robustness and we present the first ng-robust valid inequalities, the ng-CCs. This framework can facilitate the search for new ng-robust counterparts of known valid inequalities. Furthermore, we introduce different separation techniques for separating the ng-CCs and compare these numerically. We show that the separation of these cuts is equivalent to separating rounded capacity cuts on a modified graph. We present results on including the robust ng-CCs in a BPC-framework for solving CVRP benchmark instances, compared to using rounded capacity cuts. We also investigate for which types of problems these new valid inequalities outperform the rounded capacity cuts.