CVRP Solver

Pseudocode

CVRP adds a load limit to vehicle routing, so partitioning becomes bin packing and routing becomes TSP, coupled together. Clarke-Wright savings is the classic constructive method.

ClarkeWright(depot, customers, capacity):
    // Start with one dedicated route per customer
    route[i] = depot -> i -> depot   for every i

    // Saving from serving i and j on one route
    for every pair (i, j):
        saving[i][j] = d(depot,i) + d(depot,j) - d(i,j)
    sort pairs by saving, descending

    for each pair (i, j) in that order:
        if i and j are on different routes
           and both are route endpoints
           and combined demand <= capacity:
                merge the two routes

The savings formula is the whole idea: serving i and j separately costs two round trips, while serving them together replaces one outbound and one return leg with the direct hop from i to j. The saving is exactly what that substitution avoids. The capacity check is what makes this CVRP rather than plain routing, and it is why the highest-saving merge is often rejected.

Worked example, step by step

Serve four customers with vehicles of capacity 10 and see the capacity constraint override the best geometric merge.

Example graph: Depot at the origin. Customers A at distance 5 with demand 6, B at distance 5 with demand 6, C at distance 8 with demand 3 and D at distance 8 with demand 3. A and B are close together, as are C and D.

1. Start with separate routes. Four round trips: 10 + 10 + 16 + 16 = 52 in total, each vehicle carrying one customer.
2. Compute the savings. A and B are close together, so merging them saves a lot. Same for C and D. Cross pairs such as A with C are far apart and save little. Sorted by saving, the A-B merge comes first.
3. Reject the best merge. A and B have demands 6 and 6, totalling 12, which exceeds the capacity of 10. Despite being the highest-saving merge available, it is infeasible and must be skipped. This is the moment CVRP diverges from ordinary vehicle routing.
4. Accept the C-D merge. C and D have demands 3 and 3, totalling 6, comfortably within capacity. The merge is accepted and they now share a route.
5. Consider the remaining merges. A could join the C-D route only if 6 plus 6 stays within 10, which it does not. So A and B each keep their own route, and the final solution uses three vehicles.

Three routes: A alone, B alone, and C with D together. The geometrically obvious pairing of A with B is exactly the one capacity forbids, which is the defining characteristic of CVRP. An algorithm that partitions purely on distance and checks capacity afterwards will keep producing infeasible plans; capacity has to be part of the merge decision itself, not a filter applied at the end.

Complexity, and where it comes from

Time: NP-hard; O(n^2 log n) Clarke-Wright · Space: O(n^2)

Clarke-Wright computes a saving for every pair of customers at O(n squared), sorts them at O(n squared log n), and then performs a linear scan with near-constant-time route lookups, so the sort dominates at O(n squared log n). Memory holds the savings list at O(n squared). The problem is NP-hard twice over: it contains TSP through the routing decision and bin packing through the capacity-constrained partition, and neither is polynomial. Exact methods based on branch and cut and price solve instances of roughly 100 to 200 customers. Metaheuristics such as large neighbourhood search routinely reach within 1 to 2 percent of the best known solutions on instances of several thousand customers.

When to use Capacitated Vehicle Routing (CVRP), and when not to

CVRP sits in the middle of the routing family. Check which constraints your operation actually has.

Common pitfalls

• Checking capacity after partitioning rather than during. Building routes on distance alone and then repairing capacity violations produces poor solutions, because the repair undoes exactly the merges the construction most wanted. Capacity has to gate each merge as it is considered.
• Ignoring that a single customer may exceed capacity. If any customer demands more than a vehicle can carry, no feasible solution exists without splitting deliveries. Check this before solving, or the algorithm will search indefinitely for a feasible merge.
• Merging at non-endpoints. Clarke-Wright merges routes only at their endpoints, since inserting into the middle of an existing route invalidates the savings calculation. Allowing interior merges silently breaks the cost model.
• Assuming full vehicles are efficient. Packing vehicles to capacity can lengthen routes considerably, since the last customers added may be geographically remote. Minimum total distance and maximum vehicle utilisation are different objectives and often conflict.
• Overlooking fixed vehicle costs. If each vehicle carries a fixed cost, using fewer vehicles on longer routes may be cheaper overall. Optimising distance alone under-counts the true cost of the plan.

Frequently asked questions

What is the capacitated vehicle routing problem?

CVRP asks how to serve customers with known demands from a depot using a fleet of vehicles with limited capacity, minimising total travel distance. Every customer is visited exactly once, every route starts and ends at the depot, and no route may exceed vehicle capacity.

How does the Clarke-Wright savings algorithm work?

It starts with one dedicated round trip per customer, then computes for each pair the saving from serving them on a single route: the distance to each from the depot, minus the direct distance between them. Pairs are processed in descending saving order, and two routes are merged when both customers are route endpoints and the combined demand fits within capacity.

What is the difference between VRP and CVRP?

CVRP adds a capacity limit per vehicle and a demand per customer. That makes the partitioning decision a bin-packing problem alongside the routing, so the geometrically best grouping is frequently infeasible. Plain VRP partitions on geometry alone.

Why is CVRP harder than TSP?

TSP only sequences a single route. CVRP must simultaneously decide which customers share a vehicle, subject to capacity, and how to sequence each resulting route. It therefore contains both TSP and bin packing as subproblems, and the two decisions interact: the best packing is often not the best routing.

How large a CVRP instance can be solved exactly?

Exact branch-and-cut-and-price methods handle roughly 100 to 200 customers depending on structure. Beyond that, metaheuristics such as large neighbourhood search or guided local search are used, typically reaching within 1 to 2 percent of the best known solutions on instances of several thousand customers.