New Valid Inequalities for the Two-Echelon Capacitated Vehicle Routing Problem

We introduce new valid inequalities for the two-echelon variant of the Capacitated Vehicle Routing Problem (CVRP)In particular, a first group of inequalities is obtained by extending to 2E-CVRP some of the most effective among the existing CVRP valid inequalities. A second group of inequalities is explicitly derived for the 2E-CVRP and concerns the flow feasibility at customer nodes and the satellite-customer route connectivity. The inequalities are then introduced in a Branch & Cut algorithm. Computational results show that the proposed algorithm is able both to solve to optimality many open literature instances and significantly reduce the optimality gap for the remaining instances.