A new branch-and-cut algorithm for the capacitated vehicle routing problem (Q1881569)

A branch-and-cut algorithm for the capacitated vehicle routing problem is developed based on the two-index formulation. The initial LP relaxation consists of degree constraints and bounds on variables. The algorithm uses heuristic separation algorithms for rounded capacity inequalities, strengthened comb inequalities, multistar and partial multistar inequalities, a new depth-first tree search procedure for framed capacity inequalities and the first polynomial time separation heuristic for a variation of hypotour inequalities. Gomory mixed integer cuts are used at the root node. Branching is perfomed on cutsests in an order given by lower bound values. Node selection is best bound first. All cuts are kept at the root but deleted from the cut pool in other nodes following a strategy has shown to be effective in experiments. Numerical results have been performed on literature test problems and 3 problems have been solved to proven optimality for the first time.