Capacitated VRP (CVRP)

The defining feature of CVRP is that each vehicle k has a finite, non-negative capacity Q. The sum of customer demands qᵢ on any single route cannot exceed Q. This transforms the problem from a pure spatial challenge into a bin-packing and routing hybrid. A solution is infeasible if a route's total demand surpasses the vehicle's limit, regardless of how optimal the travel sequence is. This constraint is typically modeled as a knapsack-style restriction within the route construction logic.

CVRP is formally defined on a complete graph G = (V, A) where V = {0, 1, ..., n} (0 is the depot). Each customer i has a non-negative demand dᵢ. The objective is to find a set of K Hamiltonian cycles minimizing total travel cost, subject to:

• Route continuity: Each route starts and ends at the depot.
• Visit uniqueness: Each customer is visited exactly once.
• Capacity feasibility: For any route R, the sum of dᵢ for all i in R ≤ Q. This is an NP-hard problem, solvable exactly only for small instances via Mixed-Integer Linear Programming (MILP).

A common exact formulation uses binary variables xᵢⱼ equal to 1 if a vehicle travels directly from i to j. The capacity constraint is enforced using subtour elimination constraints (SECs). The standard Miller-Tucker-Zemlin (MTZ) formulation introduces auxiliary variables uᵢ representing the cumulative load after visiting customer i. The constraint uⱼ ≥ uᵢ + dⱼ - Q(1 - xᵢⱼ) simultaneously prevents subtours and enforces capacity. This compact model is suitable for MILP solvers like Gurobi.

The classic Clarke-Wright Savings Algorithm is a constructive heuristic specifically designed for CVRP. It starts with a trivial solution where each customer is served by a dedicated route. It then iteratively merges two routes (0...i,0) and (0,j...0) if the combined demand does not exceed Q. The merge is prioritized by the 'savings' value: sᵢⱼ = cᵢ₀ + c₀ⱼ - cᵢⱼ. This greedy approach quickly generates a good feasible solution, often used as a starting point for metaheuristics like Adaptive Large Neighborhood Search (ALNS).

A key distinction is between CVRP and the Split Delivery VRP (SDVRP). In CVRP, each customer's demand is indivisible and must be fulfilled by a single vehicle. This is a hard assignment constraint. In SDVRP, a customer's demand can be split across multiple vehicles, which can reduce total cost when demand exceeds vehicle capacity. CVRP is the more restrictive model, applicable when splitting a delivery is operationally impossible or cost-prohibitive, such as delivering a single palletized machine.

Standardized test instances are crucial for comparing CVRP algorithms. The most famous are the CVRPLIB datasets, including:

• Set A (Augerat et al.): Instances with 32-80 customers, widely used for exact methods.
• Set P (Christofides & Eilon): Classic instances with 50-199 customers.
• Set X (Uchoa et al.): Large-scale instances with 100-1,000 customers, designed to challenge modern metaheuristics. These datasets provide known optimal solutions, allowing researchers to benchmark the optimality gap of their heuristics.

The foundational combinatorial optimization problem from which CVRP is derived. VRP seeks the optimal set of routes for a fleet of vehicles to service geographically dispersed customers, minimizing total travel cost. CVRP adds the critical constraint of vehicle capacity, making it a more realistic model for physical goods distribution where trucks cannot carry infinite loads.

A mathematical optimization framework used to formulate CVRP as an exact model. MILP problems involve a linear objective function (e.g., minimize distance) and linear constraints, where some variables are restricted to integers—such as binary variables indicating whether a vehicle travels between two nodes. Solvers like Gurobi use Branch and Bound to find provably optimal solutions for small to medium CVRP instances.

A powerful metaheuristic widely used to solve large-scale CVRP instances where exact methods fail. ALNS iteratively improves a solution by destroying parts of routes (e.g., removing random customers) and repairing them (e.g., reinserting at lowest cost). An adaptive layer tracks the performance of different destroy/repair heuristics and selects the most effective ones, making it highly efficient for real-world logistics.

An advanced algorithm for solving large-scale CVRP formulations with an exponential number of possible routes. Instead of enumerating all routes upfront, it starts with a small subset and iteratively generates new columns (routes) with negative reduced cost by solving a pricing subproblem—often a shortest path problem with capacity constraints. This technique is foundational to state-of-the-art exact VRP solvers.

A declarative paradigm particularly effective for CVRP variants with complex side constraints. Rather than specifying a mathematical objective and constraints, you define variables, their domains, and the logical relationships between them. The solver systematically prunes infeasible assignments using propagation, excelling at problems where feasibility is as challenging as optimality, such as CVRP with time windows and driver rules.

An extension of CVRP where one or more parameters are random variables rather than fixed values. In a stochastic CVRP, customer demand might be uncertain until the vehicle arrives, requiring recourse actions like returning to the depot for restocking. This contrasts with deterministic CVRP and requires robust optimization or two-stage stochastic programming to generate routes that perform well under uncertainty.