## 4 Algorithm Design
### Hybrid Ant Colony Optimization Algorithm
#### 4.2.3 Local Search  
In this study, the initial solution generated by the HACO algorithm undergoes local search to further optimize the solution. Five local search operators are designed based on the problem and solution characteristics, and the VNS mechanism is employed for operator selection. The process begins by initializing the neighborhood counter to \(l=1\). If a local search with the specific operator improves the current solution, \(l\) remains unchanged, and the search continues within the same neighborhood. Otherwise, \(l\) is updated to \((lmodl_{max})+1\), and the search transitions to the next neighborhood. This iterative process continues until the termination criterion is satisfied. Each operator is subsequently introduced in the order of their application within the VNS framework. 1. Destroy Route: Distribution tasks should be accomplished by as few vehicles as possible. Inspired by the destruction and repair operator of the ALNS algorithm [43], this paper introduces a Destroy Route operator. This operator aims to remove one of the shortest routes from the multi-route solution and attempts to reinsert the customer nodes from that route into other routes based on the best improvement rule to minimize the number of vehicles required for the distribution tasks. Following the approach of [PERSON] et al. [44], we set a granularity threshold to restrict the search to nearby vertices, preventing wasted computation from a full route traversal without finding a feasible insertion point. The schematic diagram of Destroy Route operator is presented in Figure 7.
2. 2P-Swap: The Swap operator has been proven effective in handling EVRP [8], yet existing studies primarily rely on single-phase implementations. To address the unique challenges of this study, where swapping deployed energy replenishment infrastructures with external nodes may cause route infeasibility due to energy constraints, we propose a two-phase Swap operator (2P-Swap). The first phase exchanges customer nodes between routes to generate feasible solutions under load constraints, while the second phase swaps customer nodes and energy replenishment infrastructures  
Figure 7: The Destroy Route operator. within the same route, enhancing exploration while ensuring compliance with energy and time constraints. This approach balances solution quality and feasibility. The schematic diagram of 2P-Swap operator is presented in Figure 8.
3. 2-opt: [PERSON] et al. (2018) split a complete vehicle route into several segments by setting cut nodes at CI and then perform the best-improvement 2-opt operation on each segment to eliminate intersections. The 2-opt operator used in this study also aims for the best improvement but has a broader scope. It can be applied between any two nodes in a route that meet the criteria for the application of the operator, with the nodes being either customers or energy replenishment infrastructures. The schematic diagram of 2-opt operator is presented in Figure 9. 4. Remove Infrastructure: The initial solutions generated by the HACO algorithm, driven by pheromone updates and evaporation, exhibit inherent greediness and randomness, potentially leading to redundant energy replenishment infrastructures in the routes. Specifically, if a vehicle's remaining energy upon arriving at an infrastructure is sufficient for successive infrastructure or to return to the depot, the visit becomes unnecessary, indicating redundancy. Eliminating such infrastructures reduces intermediate energy replenishment costs and prevents unnecessary detours. The schematic diagram of Remove Infrastructure operator is presented in Figure 10.  
Figure 8: The 2P-Swap operator. Figure 9: The 2-opt operator. 5. Change Infrastructure: To further leverage the cost advantages of CI, the algorithm first identifies all BSIs along the current route. It then evaluates the feasibility of replacing each BSI with a CI, considering capacity constraints and maximum route duration. If feasible, the replacement is made, and the total route cost is recalculated.