Capacitated Vehicle Routing (CVRP)

The capacitated vehicle routing problem (CVRP) adds a load limit to each vehicle: routes must be planned so the total demand on each route never exceeds vehicle capacity. This constraint makes the problem far more realistic and harder than plain routing.

How it works

The Clarke-Wright savings heuristic remains the standard starting point, merging routes only when the combined demand fits within capacity. Sweep algorithms rotate a ray around the depot to form capacity-feasible clusters, then route each cluster as a TSP. Exact branch-and-cut-and-price solvers handle up to a few hundred customers, while modern metaheuristics such as hybrid genetic search deliver near-optimal solutions for thousands.

Applications

CVRP governs truck load planning in distribution, beverage and grocery delivery, fuel tanker scheduling, and last-mile e-commerce fulfillment where van capacity binds. Cost savings of a few percent from better routing translate into large sums at fleet scale.