Article ID: | iaor20073675 |
Country: | United States |
Volume: | 52 |
Issue: | 5 |
Start Page Number: | 723 |
End Page Number: | 738 |
Publication Date: | Sep 2004 |
Journal: | Operations Research |
Authors: | Mingozzi Aristide, Hadjiconstantinou Eleni, Baldacci Roberto |
Keywords: | networks: flow, programming: integer |
The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. In this paper, we describe a new integer programming formulation for the CVRP based on a two-commodity network flow approach. We present a lower bound derived from the linear programming (LP) relaxation of the new formulation which is improved by adding valid inequalities in a cutting-plane fashion. Moreover, we present a comparison between the new lower bound and lower bounds derived from the LP relaxations of different CVRP formulations proposed in the literature. A new branch-and-cut algorithm for the optimal solution of the CVRP is described. Computational results are reported for a set of test problems derived from the literature and for new randomly generated problems.