Capacitated VRP

CVRP is a 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. That is, CVRP is like VRP with the additional constraint that every vehicles must have uniform capacity of a single commodity.

We can find below a formal description for the CVRP:


The objective is to minimize the vehicle fleet and the sum of travel time, and the total demand of commodities for each route may not exceed the capacity of the vehicle which serves that route.


A solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route.


Let ${Q}$ denote the capacity of a vehicle. Mathematically, a solution for the CVRP is the same that VRP’s one, but with the additional restriction that the total demand of all customers supplied on a route ${R_{i}}$ does not exceed the vehicle capacity ${Q}$: ${\sum_{i=1}^{m} d_{i} \leq Q}$.