A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints

Abstract

In this paper, we present a branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which is a new problem deriving from the classical two-echelon capacitated vehicle routing problem (2E-CVRP) by considering grouping constraints in the second echelon. Customers in the 2E-CVRPGC are divided into several disjoint groups, and the grouping constraints ensure that customers from the same group are served by vehicles from the same satellite. We formulate the problem as a mixed 0–1 linear program and propose five families of valid inequalities to strengthen the model. Based on the model and the inequalities, we implement a branch-and-cut algorithm to solve the problem. The proposed branch-and-cut algorithm was evaluated on two classes of randomly generated instances. The computational results show that the five families of valid inequalities can substantially improve the lower bounds yielded by the LP relaxation of the model, and the branch-and-cut algorithm can solve more instances to optimality than CPLEX. We also conduct additional experiments to analyze the impacts of the grouping constraints on the problem, and illustrate the differences between the 2E-CVRPGC and the 2E-CVRP.