CVRP

Capacitated Vehicle Routing Problem (CVRP) is a classic optimization problem in logistics and operations research. It extends the basic Vehicle Routing Problem by introducing a capacity constraint on each vehicle: there is a depot, a fleet of identical vehicles with a fixed capacity, and a set of customers each with a nonnegative demand. Given a travel cost or distance matrix, the objective is to design routes for the vehicles so that every customer is visited exactly once, all route demands do not exceed the vehicle capacity, and all routes start and end at the depot, while minimizing total travel cost.

CVRP is NP-hard, since it generalizes the travelling salesman problem. Exact solution methods include branch-and-cut, branch-and-price, and integer programming formulations. Because of combinatorial complexity, numerous heuristics and metaheuristics are used in practice. Classic constructive heuristics include the Clarke–W Wright savings algorithm and the sweep algorithm. Metaheuristics such as genetic algorithms, tabu search, simulated annealing, ant colony optimization, and large-neighborhood search are commonly applied. Modern approaches often use hybrid methods and problem-specific neighborhood structures.

Applications span last-mile delivery, distribution logistics, service routing, and school bus routing. Variants exist: CVRPTW adds time windows; multi-depot CVRP, heterogeneous fleets with varying capacities and costs, split deliveries, stochastic or robust versions, and arc routing variants that allow multiple customers per arc. Datasets such as Solomon and Augerat benchmarks are frequently used in research to compare algorithms. Software libraries like Google OR-Tools provide CVRP solvers and examples.