Improved Branch-Cut-and-Price Algorithm for Capacitated Vehicle Routing

The best performing recent exact algorithms for the CVRP are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other  authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts. This work introduces a technique for greatly reducing the impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some much larger instances, with several hundreds customers, only considered before by heuristic methods, were solved too.