An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation
- 1 October 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 52 (5), 723-738
- https://doi.org/10.1287/opre.1040.0111
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
This publication has 31 references indexed in Scilit:
- An exact algorithm for the Traveling Salesman Problem with Deliveries and CollectionsNetworks, 2003
- On the capacitated vehicle routing problemMathematical Programming, 2003
- Multistars, partial multistars and the capacitated vehicle routing problemMathematical Programming, 2002
- Classical and modern heuristics for the vehicle routing problemInternational Transactions in Operational Research, 2000
- Routing problems: A bibliographyAnnals of Operations Research, 1995
- A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxationsAnnals of Operations Research, 1995
- A branch-and-cut algorithm for vehicle routing problemsAnnals of Operations Research, 1994
- A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windowsNetworks, 1993
- An exact algorithm for the asymmetrical capacitated vehicle routing problemNetworks, 1986
- State‐space relaxation procedures for the computation of bounds to routing problemsNetworks, 1981