Transportation Logistics & Operations Research
Clarke-Wright VRP Route Savings s_ij Formula
Calculate Geoff Clarke and John Wright’s (1964) pairwise route-consolidation distance savings s_ij = MAX(0, d_0i + d_0j - d_ij) gated by truck payload capacity Q_veh.
Rank customer route merges by triangle-inequality depot savings and truck capacity!
Geoff Clarke and John Wright (1964) created the most widely deployed heuristic in commercial vehicle routing! Starting from separate out-and-back routes Depot -> i -> Depot (2 * d_0i) and Depot -> j -> Depot (2 * d_0j) totaling 2*d_0i + 2*d_0j, linking i and j onto a single route Depot -> i -> j -> Depot (d_0i + d_ij + d_0j) saves exact distance s_ij = d_0i + d_0j - d_ij — PROVIDED combined payload q_i + q_j <= Vehicle_Capacity Q_veh and both nodes remain exterior route endpoints!
Verify across four disjoint customer pairs in A2:F5 served by a 20-pallet truck (B7 = 20): Pair_A_B (d_0i = 25, d_0j = 30, d_ij = 15, combined load 18 <= 20) saves 25 + 30 - 15 = 40 km; Pair_C_D (d_0i = 40, d_0j = 35, d_ij = 20) has a tempting 55 km raw geometric savings, but combined load 24 > 20 exceeds truck capacity (Feasible Savings = 0 km!); Pair_E_F (22 + 28 - 18, load 16 <= 20) saves 32 km; and opposite-direction Pair_G_H (15 + 15 - 30, load 12) saves 0 km! Out-and-back baseline mileage 2 * (102 + 108) = 420 km drops by 40 + 32 = 72 km to 348 km, with Top Feasible Merge = Pair_A_B (40 km)! Upgrade truck capacity in B7 to 25 pallets: Pair_C_D unlocks 55 km savings, becoming Top Merge and cutting total mileage to 293 km!
| Candidate Pair | d_0i + d_0j - d_ij (Raw km) | Combined Load (vs 20 Cap) | Feasible Savings (km) |
|---|---|---|---|
| Pair_A_B | 25 + 30 - 15 = 40 | 18 pallets (Feasible) | 40 km (Rank #1 at Q=20) |
| Pair_C_D | 40 + 35 - 20 = 55 | 24 pallets (Over Capacity!) | 0 km (55 km at Q=25) |
| Pair_E_F | 22 + 28 - 18 = 32 | 16 pallets (Feasible) | 32 km |
| Pair_G_H | 15 + 15 - 30 = 0 | 12 pallets (180-deg Opposite) | 0 km |
Capacity-Gated Clarke-Wright Savings s_ij Formula
Gate MAX(0, d_0i + d_0j - d_ij) directly by q_pair <= $B$7 so overloaded merges never pollute your INDEX/MATCH priority queue!
=IF($B$7 <= 0, "Invalid Truck Cap", IF(E2 <= $B$7, MAX(0, B2 + C2 - D2), 0))Top Priority Merge Pair & Consolidated Fleet Distance Formula
Use INDEX(A2:A5, MATCH(MAX(F2:F5), F2:F5, 0)) to identify the highest-saving capacity-feasible route consolidation.
=IF($B$7 <= 0, "Invalid Truck Cap", INDEX(A2:A5, MATCH(MAX(F2:F5), F2:F5, 0)))Try the example
Use the original values or change them to test your understanding.