H-ANTS: Hierarchical Ant System with Insert-and-Prune Charging for Capacitated Electric Vehicle Routing

Abstract

The rising popularity of electric vehicles (EVs) has led to the emergence of the capacitated electric vehicle routing problem (CEVRP), where routing decisions and charging schedules are tightly coupled. Existing single-level models suffer from complex search spaces, while decoupled models frequently yield suboptimal solutions due to myopic decision-making and weak coordination. To address these limitations, this study proposes the hierarchical ant system (H-ANTS), a hierarchical algorithm that systematically enhances the decoupled framework. At the high-level abstract planning stage, an improved max-min ant system (MMAS) is combined with a batch-improvement variable neighborhood search (BI-VNS) to generate high-quality abstract customer sequences. Subsequently, at the low-level plan refinement stage, an insert-prune heuristic (IPH) is employed, utilizing a saturate-and-prune mechanism to globally optimize charging schedules, effectively overcoming the limitations of traditional greedy repairs. The cost of the refined solution acts as a topology-aware feedback signal to guide high-level pheromone updates, enabling routing decisions to adapt effectively to energy constraints. Experimental results on benchmark instances demonstrate that H-ANTS achieves superior solution quality compared with several representative algorithms, confirming the effectiveness and practicality of the proposed method.