# Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem
## 1 Introduction  
The vehicle routing problem (VRP) has always been an important issue in logistics transportation and distribution [1]. According to different application scenarios, the VRP has inspired many variants [2]. The traditional VRP usually assumes that the demand of each customer can be completed only by one vehicle in a single service. However, in actual logistics, customer demand inevitably exceeds the maximum carrying capacity of the vehicle. At this time, it is necessary to split the customer demand. Therefore, it is of great practical significance to study the vehicle routing problem with separable demand. The split delivery vehicle routing problem (SDVRP) was first proposed in 1989 [3], and has become a new branch of vehicle routing problem. Different from the traditional vehicle routing problems, the SDVRP allows splitting the customer demands among multiple vehicles, thereby increasing the utilization of resources. The SDVRP can be described as follows: in logistics distribution, multiple customers require delivery of goods, and the company wants to assign these demands to multiple vehicles without exceeding the capacity limit of each vehicle. In such a situation, the goal is to find a set of optimal routes that satisfy all customer demands. Although the SDVRP has the NP-hard property [4], the SDVRP solution will be better than the traditional VRPsolution if the customer needs are properly split [5]. The SDVRP solution can reduce the logistics cost by reducing the transportation distance and the number of vehicles. There are two main approaches to solving VRPs: exact algorithms and heuristic algorithms. The exact algorithms are suitable for solving small-scale problems because as the problem size increases, the computation time of the algorithm significantly increases. The heuristic algorithms include traditional heuristic algorithms and metaheuristic algorithms, which are commonly used to solve larger-scale problems. The traditional heuristic algorithms include the local search algorithm [6], improved savings algorithm [7], and so on. This type of algorithm is prone to falling into local optima, making it difficult to obtain satisfactory solutions. In recent years, metaheuristic algorithms have attracted considerable attention due to their excellent performance. The currently proposed metaheuristic algorithms mainly include the tabu search algorithm [8; 9], genetic algorithm [10; 11], particle swarm optimization algorithm [12; 13], variable neighborhood search algorithm [14; 15], large neighborhood search algorithm [16; 17], ant colony algorithm [18; 19; 20], chimp optimization algorithm [21], and mayfly algorithm [22]. We focus on the ant colony algorithm because it has performed well on many optimization problems [23; 24; 25; 26]. However, existing ant colony optimization algorithms still have some problems, such as weak targeting of different customer selection strategies, difficulty in balancing convergence speed and global search ability, and susceptibility to falling into local optima. In previous studies of the ant colony algorithm, the state transition process and pheromone updating strategy were mainly improved. Setting a control threshold is a common improvement for the state transition process of an ant colony. This threshold is used to control the ants' strategy of choosing the next customer, thus enabling the algorithm to better balance convergence speed and global search ability. However, most of the existing thresholds are set to a fixed value [18; 20]. Some scholars [27] divide several fixed intervals according to the number of iterations, and different control thresholds are used in different intervals. Because the ant colony algorithm has different characteristics in different running stages, these threshold-setting methods cannot adapt to the different stages of the algorithm. Pheromones are very important in ant colony algorithms, and the improvement of pheromone processing in ant colony algorithms has been the focus of scholars.