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

Roberto Baldacci; E. Hadjiconstantinou; A. Mingozzi

doi:10.1287/opre.1040.0111

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

Roberto Baldacci¹; E. Hadjiconstantinou²; A. Mingozzi³

¹ 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

Operations Research 2004

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.

DOI: 10.1287/opre.1040.0111
Volume: 52 (5)
Pages: 723-738
Language: en
Export: BibTeX
Sources: crossref openalex