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.
Heng et al. (Wed,) studied this question.