Traffic-Informed Optimization of Last-Mile Delivery Using Hybrid Heuristic Approaches

The rapid growth of e-commerce has intensified operational and sustainability challenges in urban last-mile delivery, necessitating routing methods that perform reliably under realistic traffic and spatial conditions. This study evaluates three routing algorithms, Nearest Neighbor (NN), Clarke–WrightSavings (CWS), and Ant Colony Optimization (ACO), using 1764 real-world Amazon delivery stops grouped into ten operational clusters in the Nashville metropolitan area. Travel distances and times were obtained through the Google Maps Distance Matrix API in driving mode to reflect actual road network structure and typical traffic conditions. Substantial performance differences were observed across algorithms and cluster configurations. NN achieved a strong performance in compact clusters (18.43 miles and 58.48 min in Cluster 4) but performed poorly in dispersed clusters (82.44 miles and 196.48 min in Cluster 9), reflecting high sensitivity to spatial dispersion. In contrast, CWS consistently reduced travel distance and time across clusters, achieving the shortest observed route (18.50 miles and 47.82 min in Cluster 10). Relative to ACO, CWS reduced travel distance by up to 42% (Cluster 9) and reduced travel time by over 45% in high-dispersion clusters. ACO exhibited the highest variability, with distances reaching 98.77 miles and travel times exceeding 218 min. Multi-criteria evaluation using efficiency ratios, distributional analysis, performance quadrant visualization, and a Composite Performance Index (CPI) confirmed the dominance of CWS. CPI scores of 1.00 (CWS), 0.78 (NN), and 0.00 (ACO) reflected balanced spatial and temporal efficiency under identical traffic-informed inputs. The results demonstrate that deterministic savings-based routing provides superior stability, efficiency, and scalability in semi-static urban delivery systems. However, the present study did not benchmark the evaluated algorithms against state-of-the-art exact TSP solvers (e.g., Concorde, LKH) or more recent metaheuristics such as Genetic Algorithms or Variable Neighborhood Search. The objective was to provide a controlled empirical comparison under consistent traffic-informed cost matrices rather than to establish global optimality bounds. Consequently, while the findings strongly support the relative superiority of the Clarke–Wright Savings approach within the evaluated framework, future research incorporating advanced exact and hybrid optimization methods would further contextualize algorithmic performance.