A lagrangian relaxation approach for the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is concerned with the determination of optimal delivery routes for a fleet of capacitated vehicles, which distribute goods from a single depot to a given set of customers with known demands. Based on a two-commodity network flow, a mixed integer programming formulation for the CVRP is described in this paper. In this model, in addition to the vehicle flow, the quantity of goods transported on each edge is introduced as a continuous decision variable and is viewed as quantity flow. Further more, a new form of Miller-Tucker-Zemlin subtour elimination constraints is also proposed. Compared with the well-known exponential number of subtour elimination constraints, our model has only polynomial number of constraints. Lagrangian relaxation is used to decompose the model into two subproblems: quantity flow subproblem containing continuous variables and network flow subproblem containing binary variables, which can be solved efficiently by the linear programming and the minimum cost flow (MCF) algorithms, respectively. In last several iterations of the dual optimization, a feasible solution is constructed based on the solution of the relaxed problem. Randomly generated instances are used to evaluate the performance of the proposed algorithm with numerical results provided.