ng-Memory Based Capacity Cuts

This thesis introduces a new family of valid inequalities for the capacitated vehicle routing problem with time windows, the ng-memory based capacity cuts. These inequalities are a lifting of the ordinary capacity cuts and can be included robustly into a branch-price-and-cut algorithm if one uses the ng-route relaxation. This thesis evaluates the performance of these inequalities by solving the root node relaxation and by solving the full instance using branch-price-and-cut of several Augerat benchmark instances. Furthermore, four separate separation methods are devised to separate these new inequalities, which are all based on the CVRPSEP package for separating ordinary capacity cuts. Two of these methods guarantee that all violated ng-capacity cuts are found, provided all ordinary capacity cuts can be separated. In the root node relaxation, ng-memory based capacity cuts lifted the lower bound more than ordinary capacity cuts. For some instances, we even obtained an integer solution with the ng-cuts, whereas we did not with the capacity cuts. The fourth separation algorithm, which reduces arc flow with a factor of κ to find more violated ng-capacity cuts, achieves the highest lower bound in almost all of the instances. Furthermore, no additional violated cuts were found for κ> 4. In the branch-priceand-cut setting, we found that including ng-capacity cuts reduces the number of nodes needed in the branching tree drastically. However, no real time savings were achieved due to the longer solving time per node for the ng-capacity cuts. All in all, including ng-capacity cuts gives us higher lower bounds and reduces the number of nodes in a branching tree.