# Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem
## 4 Improved Ant Colony Algorithm
### Search Method Based on the 2-Opt Strategy  
To enlarge the search range and accelerate the convergence of the algorithm, two search methods based on the 2-opt strategy are proposed to optimize the solution after each iteration. 1. Vehicle path self-search  
In the current iterative best solution, customers on the path of each vehicle are exchanged in pairs. After the exchange, there is no need to review the carrying capacity because the vehicle carrying capacity has been reviewed in the vehicle path search, and the overall carrying capacity will be unaffected by the order of the exchanged customer points. After the exchange, the new path length is calculated. If the length is less than the current best solution, the best solution will be replaced by the currently found solution. The detailed steps of the algorithm can be seen in Algorithm 1. ```
1:Input solution \(s\);
2:Set vehicle_num = number of vehicles used in \(s\);
3:Set old_length = path length in \(s\);
4:for vehicle = 1 to vehicle_numdo
5:Set c_path = path of current vehicle;
6:while not all customer pairs in c_path have been exchanged do
7: Exchange the customer points in c_path in pairs to obtain new solution \(s\);
8: Calculate the path length new_length of the new solution \(s\);
9:if new_length < old_lengthdo
10: old_length = new_length; \(s\) = \(s\);
11:endif
12:endwhile
13:endfor
14:Output \(s\);
```  
**Algorithm 1**Vehicle path self-search  
When the number of customer points is large, if the search is carried out in each iteration, the operation efficiency of the algorithm will decrease. Therefore, it is specified to perform this search under the following conditions:  
1. Search should be performed every \(p\) iterations. After experimental verification, the best effect is achieved when the value of \(p\) is 10. 2. If the current iterative best solution is better than the global best solution, the search is performed. 2. Route search is performed between vehicles. In the current iterative best solution, customers of different vehicles are exchanged in pairs, as shown in Figure 3. The lines of different colors in the figure represent the paths of two vehicles, where \(i\) and \(j\) are customers on the respective vehicles. By swapping \(i\) and \(j\), a shorter path is obtained. This process is known as intervehicle exchange search. To ensure the minimization of the number of vehicles used, this paper adopts a simple yet effective method. When there are still customer demands, vehicles need to return to the depot only when they are fully loaded. This results in only the last vehicle potentially having leftover capacity. Because the customer demand is different, it is easy to overload one of the vehicles if customer points are exchanged between two fully loaded vehicles. In this way, new solutions are not obtained and time is consumed. Therefore, we consider only the situation where the last vehicle exchanges customer points with other vehicles. Because the last vehicle may not be fully loaded, the success rate of customer exchange is relatively high. After the exchange, the carrying capacity needs to be reviewed. If the requirements are met, the new path length will be calculated. If it is less than the current best solution, the best solution will be replaced by the newly found solution. The detailed steps of the algorithm can be seen in Algorithm 2. The execution rules of route search between vehicles are consistent with the vehicle path self-search.