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

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.