A Hybrid Clarke–Wright Savings and Simulated Annealing Algorithm in Python for the Capacitated Vehicle Routing Problem: An Application to Last-Mile E-Commerce Delivery

AbstractThe capacitated vehicle routing problem (CVRP) lies at the core of last-mile logistics, where transportation typically accounts for a large share of total fulfilment cost. Because the CVRP is NP-hard, exact methods become impractical for the instance sizes encountered in daily delivery operations, and high-quality heuristics are required. This paper presents a three-stage hybridalgorithm, implemented entirely in open-source Python, that combines the Clarke–Wright savingsconstruction heuristic, 2-opt intra-route local search, and a multi-restart simulated annealingmetaheuristic with relocate, swap, and segment-reversal neighbourhoods evaluated in constant orlinear time through delta evaluation. The contribution is not a new formulation or a new operator, buta carefully engineered, fully reproducible integration of classical components positioned as atransparent baseline for practitioners. The method is validated in two ways. On standard CVRPLIB benchmark instances (Augerat Set A) it matches the proven optimum of A-n32-k5 and attains best-of-ten gaps of 0.0–4.1% (mean gaps 1.3–4.2%) to best known solutions. On four realistic last-mile parcel-delivery instances with 25–100 customers it reduces total route distance by 21.3–29.1%relative to a capacity-constrained nearest-neighbour baseline and by up to 3.8% relative to Clarke–Wright with 2-opt. Because simulated annealing is stochastic, all results are reported as mean, standard deviation, best, worst, and 95% confidence intervals over ten independent runs, and a one-factor-at-a-time sensitivity analysis of the temperature, cooling, iteration, and restart parameters is provided together with an experimental scalability study up to 300 customers, where the fullalgorithm completes in under 1.5 seconds. A managerial analysis of the 50-customer daily operationshows that the improved routing translates into an estimated annual saving of approximately 17,600vehicle-kilometres, ₹141,000 in operating cost, and about 4.8 tonnes of CO2 emissions for a singledepot. The complete implementation and all instance data are released with the paper, so every tableand figure can be reproduced exactly.