🚚 Delivery Route Lab: Vehicle Routing, Savings and 2-opt

The science

Capacitated vehicle routing (CVRP): one depot, N stops with a parcel demand qi, identical vehicles of capacity Q. Serve every stop once with routes that start and end at the depot and never exceed Q, minimising total distance. The problem is NP-hard, so real planners use heuristics; three are compared here.

  • Nearest neighbour: from the depot always drive to the closest unserved stop that still fits in the van; start a new van when none fits.
  • Clarke-Wright savings: start with one van per stop and merge routes in order of the saving sij = d0i + d0j - dij whenever capacity allows.
  • 2-opt + relocate: inside a route, reverse a segment when dac + dbd < dab + dcd; between routes, move a single stop to a cheaper place if it fits.
  • Lower bound: each parcel must travel out and back, so L >= (2/Q) sum qi d0i. The true optimum lies between this bound and the best heuristic.

Honest simplifications: straight-line (Euclidean) distances, one map unit = 0.05 km, no road network, traffic, time windows or driver shifts; cost, speed and CO2 per km are illustrative constants, not measured emissions. Heuristics give good, not provably optimal, routes; the gap to the lower bound overstates the true gap.