Exact Solution of the Capacitated Vehicle Routing Problem

Vehicle routing problem (VRP) is a generic name given to a whole class of problems concerning the optimal design of routes to be used by a fleet of vehicles to serve a set of customers. The VRP generalizes one of the most famous and important combinatorial optimization problems: the traveling salesman problem (TSP). Since it was first proposed by Dantzig and Ramser in 1959, hundreds of papers in the areas of operations research were devoted to the exact and approximate solution of a member of the VRP class, known as the capacitated vehicle routing problem (CVRP), where a homogeneous fleet of vehicles is available and the only constraint considered is the vehicle capacity constraint. Real-world applications of the VRP are, for instance, delivery and collection of goods, solid waste collection, street cleaning, school bus routing, dial-a-ride systems, transportation of handicapped persons, and routing of salesmen and of maintenance units. This article provides a review of the developments that had a major impact in the current state-of-the-art of exact algorithms for the CVRP. The paper also reports a comparison of the computational performances of the recent exact methods.