ng-Memory Based Capacity Cuts
Ymro Hoogendoorn  1, *@  , Kevin Dalmeijer  1@  
1 : Econometric Institute, Erasmus University Rotterdam
* : Corresponding author

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.

Online user: 1 RSS Feed