Capacitated VRP (CVRP)

The CVRP is a Vehicle Routing Problem (VRP) in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. In other words, the CVRP is the basic VRP with the additional constraint that every vehicle has the same uniform capacity for a single commodity. It is the most studied member of the VRP family and the benchmark against which most new exact and heuristic methods are evaluated.

Formal description

• Objective: minimize the vehicle fleet and the sum of the travel time, such that the total demand of the commodities delivered on each route does not exceed the capacity of the vehicle that serves that route.
• Feasibility: a solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle that services the route.
• Formulation: let denote the capacity of a vehicle. Mathematically, a solution of the CVRP is the same as for the VRP, with the additional restriction that the total demand of all customers supplied on a route does not exceed the vehicle capacity :

The CVRP generalizes the Traveling Salesman Problem (a single uncapacitated vehicle), and its routing-and-loading structure connects it closely to the Bin Packing Problem. A large collection of standard test instances is available in our CVRP instances section.

See also: VRP formulation · Multi-Depot VRP · VRP with Time Windows · CVRP benchmark instances