A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs

Matteo Fischetti, Paolo Toth and Daniele Vigo
Additional contact information
Matteo Fischetti: DEI, University of Padova, Padova, Italy
Paolo Toth: DEIS, University of Bologna, Bologna, Italy
Daniele Vigo: DEIS, University of Bologna, Bologna, Italy

Operations Research, 1994, vol. 42, issue 5, 846-859

Abstract: We consider the asymmetric capacitated vehicle routing problem ( CVRP ), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP , based on the so-called additive approach . Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP . Effective implementations of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature.

Keywords: programming; algorithms: bounding procedures; branch-and-bound algorithms; transportation: asymmetric capacitated vehicle routing (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.5.846 (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:oropre:v:42:y:1994:i:5:p:846-859

Access Statistics for this article

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