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
json{ "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
