Capacitated VRP (CVRP)

The defining feature of CVRP is a hard capacity limit (weight, volume, or pallet count) assigned to every vehicle in the fleet. A route becomes infeasible the moment the cumulative demand of assigned customers exceeds this limit. This constraint forces the algorithm to balance spatial proximity against load consolidation, often creating counter-intuitive routes where a nearby customer is skipped to avoid overloading a vehicle.

CVRP is often introduced with a homogeneous fleet—all vehicles have identical capacity. This simplifies the mathematical formulation. The more complex Heterogeneous Fleet VRP (HFVRP) is a direct extension where vehicles have different capacities and costs. In HFVRP, the solver must simultaneously decide which vehicle type to assign to a route, adding an asset selection layer to the loading constraint.

Solving a CVRP requires simultaneously answering two interdependent questions:

• Assignment: Which customers are grouped together on a single route?
• Sequencing: In what order should the vehicle visit them to minimize distance? The capacity constraint tightly couples these decisions. A poor assignment that groups high-demand customers together forces inefficient, long-distance sequencing. This interdependence makes CVRP an NP-hard combinatorial optimization problem, requiring heuristics for real-world scale.

CVRP is typically formulated as a Mixed Integer Programming (MIP) model on a graph where nodes represent the depot and customers. Key constraints include:

• Flow conservation: A vehicle entering a node must leave it.
• Subtour elimination: Prevents disconnected loops that don't include the depot.
• Capacity constraint: The sum of demand along a route ≤ vehicle capacity Q. The capacity constraint is often expressed as: Σ d_i * y_ik ≤ Q for each vehicle k, where d_i is customer demand and y_ik indicates assignment.

Classic CVRP enforces a single-source constraint: each customer's entire demand must be fulfilled by exactly one vehicle visit. Relaxing this rule leads to the Split Delivery VRP (SDVRP). In SDVRP, a customer's demand can be divided among multiple vehicles. While this adds complexity, it can significantly reduce total fleet mileage, especially when individual customer demands are large relative to vehicle capacity.

The foundational combinatorial optimization challenge from which CVRP derives. VRP seeks the optimal set of routes for a fleet of vehicles to service a geographically dispersed set of customers, starting and ending at a central depot. The primary objective is typically to minimize total distance or travel time. CVRP adds the critical dimension of vehicle capacity, transforming a purely spatial problem into one with loading constraints.

A VRP variant where goods must be transported between specific pickup and delivery pairs, enforcing strict precedence constraints—a pickup must occur before its associated delivery. When combined with vehicle capacity limits, it becomes the Capacitated PDP. This is critical for courier services and less-than-truckload (LTL) operations. Key constraints include:

• Pairing: A single vehicle handles both pickup and delivery.
• Precedence: Pickup visit must precede delivery visit.
• Capacity feasibility: The vehicle's load must never exceed its limit at any point along the route.

Also known as the Mixed Fleet VRP, HFVRP generalizes CVRP by introducing a fleet with non-identical vehicles. Each vehicle type k has a distinct capacity Q_k, fixed cost, and variable cost per unit distance. The solver must simultaneously decide on the optimal fleet composition and routing. This adds a strategic asset utilization layer to the tactical routing decisions of standard CVRP, often modeled with a two-commodity flow formulation.

A dominant metaheuristic for solving large-scale CVRP instances where exact methods fail. LNS iteratively destroys a significant portion of a current solution (e.g., removing 30% of customer visits) and then repairs it using a constraint programming solver or greedy insertion heuristic. The key advantage is its ability to escape deep local optima. Adaptive LNS (ALNS) extends this by dynamically selecting from a portfolio of destroy and repair operators based on their historical success, significantly outperforming static heuristics on benchmark datasets like Solomon's instances.