Optimizing Electric Delivery Vehicle Route Planning: A Hybrid Approach Integrating Clustering and Ant Colony Algorithm for Sustainable Transportation

The transition to electric vehicles (EVs) in urban logistics presents complex operational challenges, driven primarily by limited battery capacities, charging station scheduling, and dynamic traffic congestion. This paper introduces a framework to solve the Capacitated Multi-Depot Electric Vehicle Routing Problem (MD-EVRP). We propose a novel Multi-Depot Rotational Sweep Cluster K-means (MD-RSCK) algorithm to partition large-scale spatial data while strictly adhering to vehicle capacity constraints. To optimize intra-cluster routing, we develop an Ant Colony Optimization (ACO) engine augmented with a Time-Dependent Congestion Model. Furthermore, the framework integrates an Energy-Aware Route Refiner (EARR). This architecture utilizes recursive backtracking to ensure battery-feasible routes, adapting to both symmetric Euclidean approximations and real-world asymmetric traffic networks. The framework is evaluated against standard IEEE EVRP benchmarks and a multi-depot urban case study based on the road network of Shanghai, China. Experimental results demonstrate that this integrated architecture achieves competitive distance and cost metrics within a 2.44% optimality gap of state-of-the-art algorithms while ensuring strictly feasible battery states and preventing cyclic entrapment, providing a scalable operational tool for modern sustainable logistics.