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

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.