This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Baldacci, R. Articles by Mingozzi, A. Search for Related Content

An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation

DISMI, University of Modena and Reggio Emilia, Viale A. Allegri, 15, 42100 Reggio Emilia, Italy
Imperial College, Management School, Exhibition Road, London SW7 2PG, United Kingdom
Department of Mathematics, University of Bologna, Via Sacchi 3, 47023 Cesena, Italy
baldacci.roberto{at}unimore.it
e.hconstantinou{at}imperial.ac.uk
mingozzi{at}csr.unibo.it

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.

Subject classifications: programming; integer; two-commodity formulation; programming; integer; cutting plane; branch-and-cut algorithm; transportation; capacitated vehicle routing.
History: Received October 2000; revision received January 2003; revision received April 2003; accepted May 2003.

This article has been cited by other articles:

				R. Baldacci, M. Dell'Amico, and J. S. Gonzalez The Capacitated m-Ring-Star Problem Operations Research, November 1, 2007; 55(6): 1147 - 1162. [Abstract] [PDF]