A Granular Ball–Ant Colony Optimization Framework Enhanced by Variable Neighborhood Search for the Multi-Depot Half-Open Time-Dependent EVRP (2026)

Annual Conference on Genetic and Evolutionary Computation

Authors

Yingkai Xu, Anikó Kopacz, Camelia Chira

Abstract

The widespread adoption of electric vehicles (EVs) in urban logistics has led to the Electric Vehicle Routing Problem (EVRP) emerging as a prominent topic in combinatorial optimization research. To improve the efficiency of urban logistics distribution and minimize operational costs, the Multi-Depot Half-Open Time-Dependent Electric Vehicle Routing Problem (MDHOTDEVRP) is examined, where EVs may return to the nearest depot after completing deliveries instead of returning to their initial depot. This study proposes a Granular Ball-Ant Colony Optimization algorithm with Variable Neighborhood Search (GBACO-VNS) to address the MDHOTDEVRP. The approach extends the original GB-ACO framework by integrating a variable neighborhood search (VNS) mechanism to break the rigidity of routes and granular ball structures. The integration of VNS enhances exploration of the solution space and helps escape local optima. Furthermore, a range anxiety (RA) model is introduced to guide charging decisions based on drivers’ anxiety levels during travel, which better reflects real-world operational conditions. The experimental results indicate that GBACO-VNS substantially improves quality of the solution compared to several optimization algorithms while maintaining computational efficiency. These findings confirm its effectiveness for the EVRP and establish an efficient algorithmic framework for addressing complex EVRPs.

Citation

@Inproceedings{Xu2026AGB,
 author = {Yingkai Xu and Anikó Kopacz and Camelia Chira},
 booktitle = {Annual Conference on Genetic and Evolutionary Computation},
 title = {A Granular Ball–Ant Colony Optimization Framework Enhanced by Variable Neighborhood Search for the Multi-Depot Half-Open Time-Dependent EVRP},
 year = {2026}
}