This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Achuthan, N. R. Articles by Hill, S. P. Search for Related Content

An Improved Branch–and–Cut Algorithm for the Capacitated Vehicle Routing Problem

Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845
Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845
Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845
n.r.achuthan{at}curtin.edu.au
caccetta{at}maths.curtin.edu.au
hillsp{at}maths.curtin.edu.au

The capacitated vehicle routing problem (CVRP) deals with the distribution of a single commodity from a centralized depot to a number of specified customer locations with known demands. The CVRP considered in this paper assumes common vehicle capacity, fixed or variable number of vehicles, and an objective to minimize the total distance traveled by all the vehicles. This paper develops several new cutting planes for this problem, and uses them in an exact branch–and–cut algorithm. Two of the new cutting planes are based on a specified structure of an optimal solution and its existence. Computational results are reported for 1,650 simulated Euclidean problems as well as 24 standard literature test problems; solved problems range in size from 15–100 customers. A comparative analysis demonstrates the significant computational benefit of the proposed method.

History: Received: July 1996; revised: June 1999; revised: October 2001; accepted: February 2002.