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.
sij = d0i + d0j - dij whenever capacity allows.dac + dbd < dab + dcd; between routes, move a single stop to a cheaper place if it fits.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.