An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation

An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation

0.00 Avg rating0 Votes
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: , ,
Keywords: networks: flow, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.