A Hybrid Granular Ball-Ant Colony Optimization for the Multi-Depot Half-Open Time-Dependent Electric Vehicle Routing Problem

Electric vehicles (EVs) are increasingly utilized in logistics and distribution to expedite achieving carbon peaking and neutrality goals, drawing considerable attention to the Electric Vehicle Routing Problem (EVRP). This study investigates the Multi-Depot Half-Open Time-Dependent Electric Vehicle Routing Problem (MDHOTDEVRP) and aims to improve coordination and distribution efficiency among logistics depots. This problem involves multiple depots, with EVs allowed to return to the nearest depot after completing their distribution tasks. We propose a hybrid method to solve the MDHOTDEVRP by integrating granular ball (GB) computing with the Ant Colony Optimization (ACO) algorithm. Firstly, enhanced k-means clustering is utilized to allocate customers to EVs. Then, customers within each cluster are subdivided into multiple GBs, with the paths of these GBs being scheduled. Finally, the ACO algorithm establishes routes within each GB. Experimental results indicate that the proposed GB-ACO algorithm efficiently allocates charging stations and plans distribution routes in scenarios with clustered distributions.