The Sittingbourne projectThe Clarke-Wright savings algorithm: filling a van sensibly
One depot, 161 stops, 21,414 leaflets and a van that cannot take them all at once.
The ONS splits the Sittingbourne built-up area into 162 census output areas and publishes a centre point for each; by our sum of the area counts they hold 21,521 households. The learner sets up an imaginary leaflet drop: one leaflet per household, left as a bundle at each area's centre. The area whose centre is closest to the average of all the centres becomes the depot, leaving 161 stops that need 21,414 leaflets in all. The van holds 3,000. The worst plan is a separate out-and-back trip for every stop, which comes to 478.2 km in straight lines.
The savings idea is one line of arithmetic. If stops A and B are each served alone, the van drives depot to A and back, then depot to B and back. Serve them on one trip and it drives depot, A, B, depot. The saving is the distance from the depot to A, plus the depot to B, minus A to B. The program works this out for all 12,880 pairs of stops, sorts them with the largest saving first, and goes down the list joining trips end to end whenever the combined load still fits. The largest saving was 5.09 km, for two stops about 2.6 km and 3.1 km from the depot and only 0.54 km from each other.
Total distance to serve all 161 stops, straight-line, our Python run| Van capacity | Closest-next rule | Clarke-Wright savings |
|---|
| 2,000 leaflets | 11 trips, 81.5 km | 12 trips, 64.1 km |
| 3,000 leaflets | 8 trips, 64.7 km | 8 trips, 53.8 km |
| 5,000 leaflets | 5 trips, 56.8 km | 5 trips, 45.5 km |
The closest-next rule is what most people would try first: drive to the closest stop that still fits in the van, and go home when nothing fits. With a capacity of 3,000 it needs 8 trips and 64.7 km. The savings method also needs 8 trips but covers 53.8 km, about 17% less, after 153 joins. The 2,000 row holds a surprise. Eleven trips are the fewest that could carry 21,414 leaflets, and the closest-next rule manages it, but the savings method uses 12 trips and still drives less: 64.1 km against 81.5 km. Fewer trips and less distance are different goals, and the algorithm only ever chased distance.
Neither method is proved to give the shortest plan, and the distances are straight lines between area centres, not roads. The leaflet drop and the van sizes are invented for the exercise; the households and locations are real.
Ages 8 to 11
Plan deliveries on a paper map with a toy van that holds five parcels, and compare plans by total distance.
Ages 11 to 15
Compute the saving for every pair of stops in Python and sort the list.
Ages 15 and up
Code the full method with the capacity check, then test it against the closest-next rule at three van sizes.
What is real and what is ours
Household counts are Census 2021 figures from Nomis and the centre points are ONS population-weighted centroids, both Office for National Statistics data under the Open Government Licence. The depot choice, the leaflet scenario, the capacities and every distance are our own.
