Vehicle Routing Problem (VRP)

Overview

VRP determines optimal routes for a fleet of vehicles to serve a set of customers from a depot, minimizing total distance or cost. NP-hard — exact solutions only feasible for small instances (< 25 nodes). Practical solutions use heuristics (Clarke-Wright savings, sweep) or metaheuristics (simulated annealing, genetic algorithm).

When to Use

Trigger conditions:

Planning daily delivery routes for a fleet of vehicles
Minimizing total travel distance/time under capacity constraints
Optimizing route assignments across multiple vehicles

When NOT to use:

For single-vehicle route optimization (use TSP solvers)
For real-time dynamic routing with continuous order arrivals (use online algorithms)

Algorithm

IRON LAW: VRP Is NP-Hard — Exact Solutions Don't Scale
For n customers, the solution space grows factorially. Exact methods
(branch and bound) work for n < 25. For real-world problems (50-1000+
customers), heuristics are REQUIRED. A good heuristic solution within
5% of optimal is far more valuable than an optimal solution that takes
hours to compute.

Phase 1: Input Validation

Collect: depot location, customer locations and demands, vehicle capacity, number of vehicles, time windows (if applicable), distance/time matrix. Gate: All locations geocoded, demand doesn't exceed vehicle capacity per customer.

Phase 2: Core Algorithm

Clarke-Wright Savings Heuristic:

Start with each customer on its own route (depot → customer → depot)
Compute savings for merging route pairs: s(i,j) = d(depot,i) + d(depot,j) - d(i,j)
Sort savings descending
Merge routes greedily if capacity constraint allows
Improve with 2-opt (swap edges within routes) and or-opt (move customers between routes)

Phase 3: Verification

Check: all customers visited exactly once, no vehicle exceeds capacity, all routes start and end at depot. Compare total distance against lower bound. Gate: All constraints satisfied, solution within 10% of lower bound.

Phase 4: Output

Return routes with sequence, distance, and load.

Output Format

{
  "routes": [{"vehicle": 1, "sequence": ["depot", "C3", "C7", "C1", "depot"], "distance_km": 45, "load": 850, "capacity": 1000}],
  "summary": {"total_distance_km": 180, "vehicles_used": 4, "utilization_avg": 0.82},
  "metadata": {"customers": 30, "method": "clarke_wright_2opt", "computation_ms": 150}
}

Examples

Sample I/O

Input: 10 customers, 2 vehicles (cap=500), depot at center Expected: 2 routes, each serving ~5 customers, total distance minimized by geographic clustering.

Edge Cases

Input	Expected	Why
One customer demand > capacity	Infeasible or split delivery	Need split delivery VRP variant
All customers co-located	Minimal routing, capacity-limited trips	Distance is trivial, trips determined by load
Tight time windows	More vehicles needed	Time constraints may prevent full-capacity routes

Gotchas

Distance matrix quality: Road distance ≠ Euclidean distance. Use actual road network distances (Google Maps, OSRM) for practical routing.
Time windows add complexity: VRPTW (VRP with Time Windows) is significantly harder. Customers requiring specific delivery windows fragment routes.
Dynamic vs static: Real-world routing has cancellations, additions, and traffic. Plan static routes but allow dynamic re-optimization.
Driver constraints: Maximum driving hours, break requirements, and overtime costs add practical constraints not in the basic model.
Return to depot: Standard VRP assumes routes return to depot. Open VRP (routes end at last customer) needs different formulation.

References

For Clarke-Wright algorithm implementation, see references/clarke-wright.md
For metaheuristic approaches (SA, GA), see references/metaheuristics.md

algo-sc-routing