Robust branch-and-cut-and-price for the capacitated vehicle routing problem (Q2492675)

The authors present a branch-and-cut-and-price algorithm for the capacitated vehicle routing problem (CVRP). They combine two CVRP formulations, one using bound, degree, and capacity constraints and one using \(q\)-routes to formulate a Dantzig-Wolfe master problem which has exponentially many variables and constraints. The column generation procedure is solved using dynamic programming and generates \(s\)-cycle free \(q\)-routes for small values of \(s\). Heuristics are used to speed up the dynamic programming procedure. Several known types of cuts are employed. An exact separation procedure for rounded capacity cuts is used to compute lower bounds for the first and combined CVRP formulation to be used in a heuristic separation procedure. Details on the representation of variables and constraints and dynamic selection of column generation are given. The numerical results show that all literature instances up to 135 customers are solved optimally. 18 instances are solved to optimality for the first time.