An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation
成果类型：
Article
署名作者：
Baldacci, R; Hadjiconstantinou, E; Mingozzi, A
署名单位：
Universita di Modena e Reggio Emilia; Imperial College London; University of Bologna
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0111
发表日期：
2004
页码：
723-738
关键词：
摘要：
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.