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

N. R. Achuthan (), L. Caccetta () and S. P. Hill ()
Additional contact information
N. R. Achuthan: Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845
L. Caccetta: Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845
S. P. Hill: Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia 6845

Transportation Science, 2003, vol. 37, issue 2, 153-169

Abstract: 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.

Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.37.2.153.15243 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:37:y:2003:i:2:p:153-169

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().