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

R. Baldacci (), E. Hadjiconstantinou () and A. Mingozzi ()
Additional contact information
R. Baldacci: DISMI, University of Modena and Reggio Emilia, Viale A. Allegri, 15, 42100 Reggio Emilia, Italy
E. Hadjiconstantinou: Imperial College, Management School, Exhibition Road, London SW7 2PG, United Kingdom
A. Mingozzi: Department of Mathematics, University of Bologna, Via Sacchi 3, 47023 Cesena, Italy

Operations Research, 2004, vol. 52, issue 5, 723-738

Abstract: 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.

Keywords: programming; integer; two-commodity formulation; programming; integer; cutting plane; branch-and-cut algorithm; transportation; capacitated vehicle routing (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (50)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0111 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:5:p:723-738

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().