"algo-sc-routing"

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:

1. Start with each customer on its own route (depot → customer → depot)
2. Compute savings for merging route pairs: s(i,j) = d(depot,i) + d(depot,j) - d(i,j)
3. Sort savings descending
4. Merge routes greedily if capacity constraint allows
5. 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.