That puzzle is the capacitated vehicle routing problem. It is also computationally hard: researchers classify it as strongly NP-hard, so exact methods strain as instances grow.
This guide covers the CVRP definition, its mathematical formulation, exact and heuristic solving methods, solver options, and the steps from a textbook model to a production routing system.
Key Takeaways
- CVRP adds vehicle capacity to routing: every route must serve demand without overloading its truck.
- A full model needs a network, demands, capacity, variables, an objective, visit rules, flow conservation, and subtour prevention.
- Exact solvers can prove optimality on smaller instances; heuristics deliver strong answers faster at scale.
- Time windows, traffic, and dynamic orders often push you past basic CVRP.
What Is the Capacitated Vehicle Routing Problem?
Definition and core assumptions
CVRP starts with a depot, known customer demands, a vehicle capacity, and travel costs. The goal: find minimum-cost routes, each starting and ending at the depot, so every customer is served once and no route exceeds capacity.
Baseline assumptions usually include:
- Known, indivisible customer demand
- A fixed or bounded fleet
- A travel-cost matrix between all nodes
- Identical vehicle capacities, unless the model states otherwise
CVRP compared with related routing models
The Traveling Salesperson Problem builds one tour for one vehicle. CVRP must also partition customers across a fleet, which is what makes capacity binding. The broader VRP family adds options such as time windows, mixed fleets, open routes, pickup-and-delivery pairs, and split deliveries. None of these belong to the basic CVRP definition.
When CVRP is the right abstraction
CVRP fits when capacity is your primary constraint. A beverage distributor loading identical trucks from one warehouse is a good example. Before you commit, list every other rule your operation enforces. Delivery windows or truck restrictions mean the basic model is only a starting point.
CVRP Mathematical Formulation
Define the network, parameters, and indexing
Model a graph with a depot (node 0), customers 1 to n, a vehicle set K, demand q_i per customer, capacity Q, and travel cost c_ij between nodes. Keep units consistent: demand and capacity must use the same unit, such as pounds or pallets.
Fix these inputs before solving:
- Number of vehicles
- Whether vehicles are identical
- Whether every vehicle returns to the depot
- Whether costs are symmetric
Choose decision variables
The classic three-index form uses a binary x_ijk equal to 1 if vehicle k drives from i to j, plus y_ik for whether vehicle k serves customer i. This traces to Golden, Magnanti, and Nguyen (1977). The two-index form drops the vehicle index, using x_ij alone, and is generally favored for identical vehicles.
Load variables u_i record cumulative load after visiting node i. They tie demand to capacity: along any used arc, load must grow by at least the next customer's demand.
Set the objective function
The base objective minimizes the sum of c_ij · x_ij, where cost is distance, time, or money. Practical models add penalties for fleet size, late service, emissions, or unbalanced routes.
Weights matter. A heavy fixed cost per vehicle pushes the solver toward fewer, fuller routes even if total distance rises. A heavy balance penalty does the reverse. Test weights on a sample day and inspect the routes before trusting them.
Add routing and capacity constraints
- Visit rule: each customer has exactly one incoming and one outgoing arc (degree 2 in the undirected two-index form).
- Flow conservation: a vehicle entering a customer must leave it.
- Depot rule: at most m vehicles leave the depot, and all return.
- Capacity: total demand on any route is at most Q. With split deliveries, demand can divide across vehicles and the visit rule relaxes.
Prevent subtours and compare formulations
Without extra constraints, a solver may create disconnected cycles that never touch the depot. They satisfy degree rules but are useless. Three common fixes exist:
| Approach | Idea | Trade-off |
|---|---|---|
| Miller–Tucker–Zemlin (MTZ) | Load variables: u_j ≥ u_i + q_j − Q(1 − x_ij) | Compact and easy to code; weak relaxation |
| Single-commodity flow | Flow variable f_ij ≤ Q · x_ij carries remaining load | Compact; stronger or equal bounds in published comparisons |
| Rounded capacity cuts | For customer subset S: x(δ(S)) ≥ 2⌈q(S)/Q⌉ | Strong, but added dynamically in branch-and-cut |
A tiny symbolic case shows the idea. With customers 1 and 2, each with demand 6 and Q = 10, the cut for S = {1, 2} requires x(δ(S)) ≥ 2⌈12/10⌉ = 4. Two vehicles must serve them, so a single cycle through both is cut off.
No option wins universally. MTZ is clearest, and cuts scale best in exact solvers.
How to Solve CVRP
Exact optimization methods
Mixed-integer programming, branch-and-bound, branch-and-cut, and branch-cut-and-price search the space while tracking a lower bound. If the incumbent (best feasible solution) meets the bound, you have proof of optimality.
Exact work has reached classical instances with up to 420 customers. That is a historical result, not a ceiling. When the clock runs out, you keep the incumbent and report the gap between it and the best bound.
Construction and improvement heuristics
Constructive methods build a feasible starting set of routes quickly:
- Clarke–Wright savings: merge routes where combining saves the most distance
- Sweep: group customers by polar angle around the depot, cutting at capacity
- Nearest insertion: add the cheapest-to-place customer to a route
Improvement operators then refine them. Relocate moves a customer, swap exchanges two, and 2-opt reverses a segment. Each move is accepted only if capacity stays feasible and cost drops.
Metaheuristics and hybrid approaches
Metaheuristics escape local optima:
- Tabu search forbids recently reversed moves
- Simulated annealing sometimes accepts worse moves, less often over time
- Genetic algorithms recombine routes from a population; hybrid genetic search adds local search and the SWAP* neighborhood
- Adaptive large neighborhood search removes and reinserts customers, shifting weight toward operators that work
Published literature does not establish a shared ranking among them. Matheuristics pair a heuristic start with exact optimization on selected route segments.
Evaluate solution quality correctly
A fast feasible answer is not a proven optimum. Track these separately:
- Feasibility and capacity violations
- Objective value and runtime
- Lower bound and optimality gap
- Repeatability across random seeds
A gap against a best-known solution differs from a gap against a proven bound. The 2026 benchmark report records proofs for only 61 of 100 X instances, so a best-known solution is not always proven optimal. Report per-route and fleet-level numbers: distance or time, vehicles used, unserved demand, and penalty terms.
Match the method to the operational context
| Situation | Leaning |
|---|---|
| Small static plan, proof wanted | Exact or branch-and-cut |
| Hundreds of stops, nightly planning | Metaheuristic or hybrid |
| Same-day orders, traffic updates | Fast heuristics with reoptimization |
Dynamic settings matter most. Optimal for the current state does not stay optimal once new orders arrive. A nightly planning method can be wrong for dispatch.
CVRP Solver Options and Selection Criteria
Compare representative solver categories
These tools solve different layers of the problem:
| Tool | Type | Notes |
|---|---|---|
| Google OR-Tools | Routing library | C++, Python, Java, C#; Apache 2.0 |
| Gurobi, CPLEX | Commercial MILP engines | You supply the formulation; commercial licensing |
| PyVRP | Open-source Python | MIT; CVRP, time windows, mixed fleets |
| jsprit | Open-source Java | Apache 2.0; maintained by GraphHopper |
| VROOM | Open-source C++ | BSD-2-Clause; supports open trips |
Verify language support, constraint coverage, license, and maintenance before committing. Split-delivery support is not clearly documented for these tools, so confirm it directly if you need it. The best solver depends on your formulation and deployment needs, not tutorial popularity.
Benchmark solvers on the same problem
Use identical coordinates, matrices, demands, capacities, constraints, stopping rules, and hardware. Compare:
- Feasibility rate and route quality
- Runtime and memory
- Optimality gap, where available
- Stability across runs
- Ease of feeding output into dispatch systems
The DIMACS challenge scored teams on a primal integral, which blends solution quality with timing rather than final cost alone. That approach suits any benchmark.
Check production and integration requirements
Look for custom cost matrices, truck restrictions, time-dependent travel, warm starts, incremental reoptimization, SDK support, cloud or on-premise deployment, and transparent pricing.
Keep the optimization engine separate from your map data. Boyaci, Dang, and Letchford found Euclidean approximation acceptable in some settings but not all. Replacing straight lines with real road paths can make time-window routes infeasible. Poor geocodes or stale matrices undermine a sound solver.
Position NextBillion.ai as a production routing option
NextBillion.ai is an API-first route optimization platform for logistics, fleet, delivery, and field service teams. Its Route Optimization API supports 50+ hard and soft constraints, including vehicle capacity, custom distance and duration matrices, and a truck mode with vehicle dimensions. Pricing can be per vehicle or per order rather than per API call, and deployment includes cloud or on-premise options.
Treat that as a starting point, not a verdict. Run a trial against your own demand patterns, vehicle rules, and service levels.
Implementing CVRP in Real-World Operations
Prepare and validate the input data
Check before solving:
- Coordinates and depot locations are valid and not duplicated
- Demand and capacity use the same units
- No negative or missing demands
- Vehicle counts are realistic
- Travel matrices are current
An apparently infeasible model often has a unit mismatch, such as demand in cases and capacity in pounds, not a bad algorithm.
Customers whose single demand exceeds Q are another common culprit.
Test the model incrementally
Start with a small instance you can verify by hand. Then add customers, vehicles, constraints, and penalties one at a time.
Write tests for:
- Every customer is covered exactly once
- Each route is continuous and returns to the depot
- No route exceeds capacity
- No subtours exist
When the model reports infeasibility, relax constraints one at a time to find the offender.
Extend CVRP to operational requirements
Real operations rarely stay at basic CVRP. Time windows, service durations, driver-hour limits, mixed fleets, pickups, and dynamic orders each call for a variant or broader model.
Ichoua, Gendreau, and Potvin warn that constant travel times can yield suboptimal or infeasible plans once traffic varies.
Judge results by operational KPIs, not distance alone:
- On-time service rate
- Total driving time
- Vehicle utilization
- Unserved orders
- Dispatcher acceptance of the plan
Fuel use is worth tracking too, though your solver may not report it directly.
Frequently Asked Questions
How do you solve the capacitated vehicle routing problem?
Define the network, demands, and capacity, then add routing, capacity, and subtour constraints. Choose exact, heuristic, metaheuristic, or hybrid solvers based on problem size and operational needs.
What is the capacitated vehicle routing problem?
CVRP assigns customer visits to depot-based vehicles so each route stays within vehicle capacity while minimizing a stated objective such as distance, time, or cost.
Is the capacitated vehicle routing problem NP-hard?
Yes, it is classified as strongly NP-hard. Exact methods become impractical as customers and constraints multiply, which is why heuristics dominate large-scale use.
What is the difference between CVRP and VRP?
VRP is the broad family of fleet routing problems. CVRP is one variant that adds vehicle-capacity constraints; others add time windows, mixed fleets, or pickups.
Which solver is best for a capacitated vehicle routing problem?
It depends on scale, constraint complexity, optimality needs, response time, integration, and licensing. Benchmark a few representative solvers on your own data.
