# Path Optimization of Joint Delivery Mode of Trucks and UAVs

Authors: Qingkui Cao; Xuefei Zhang; Xiangyang Ren
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

With the development of e-commerce and information technology, new modes of distribution are emerging. A new type of distribution tool, UAV (unmanned aerial vehicle), has entered into the public’s field of vision. In the background of growing e-commerce, this paper proposes a new delivery mode of joint delivery of trucks and UAVs which particularly has been popular in recent years, with the advantages of prompt delivery, low cost, and independence from terrain restrictions, while traditional transportation tools such as trucks have more advantages in terms of flight distance and load capacity. Therefore, the joint delivery mode of trucks and UAVs proposed in this paper can well realize the complementary advantages of trucks and UAVs in the distribution process and consequently optimize the distribution process. Moreover, the growing e-commerce promotes customers’ higher needs for delivery efficiency and the integrity of the delivered goods which urges companies to pay more attention to customers’ satisfaction. This paper analyzes the joint delivery mode of trucks and UAVs, aims to minimize total delivery cost and maximize customer satisfaction, and builds a multiobjective optimization model for joint delivery. Furthermore, an improved ant colony algorithm is proposed in order to solve the mode in this paper. In order to effectively avoid prematurity of the ant colony algorithm, the limited pheromone concentration and the classification idea of the artificial bee colony algorithm are introduced to improve the ant colony algorithm. Finally, some experiments are simulated by MATLAB software, and the comparison shows that the joint delivery of trucks and UAVs has more advantages, and the improved ant colony algorithm is more efficient than the traditional ant colony.


---

## Body

## 1. Introduction

Recently, the application of UAVs has remained high heat and has been widely used in people’s daily life and public services. On one hand, UAVs are not restricted by geographical conditions or road conditions and can greatly expand the efficiency of space usage. In urban areas with traffic congestion, remote areas with complex terrain, or disaster areas with dynamic environmental changes, they can respond quickly. On the other hand, UAVs are highly flexible and do not require a dedicated pilot, making them easy to operate and significantly reducing manpower costs. In addition, UAVs use batteries as a power source, making them more energy efficient and environmentally friendly. Being battery-powered and the small size make the UAVs limited in range and vulnerable to outside interference [1]. However, some tasks require ground coordination, such as logistics delivery, rescue, and target tracking, which require vehicles and UAVs to work together [2]. In the logistics distribution process, the joint delivery model of trucks and UAVs not only reduces the delivery tasks of trucks but also improves the efficiency. It has significant economic advantages. Trucks and UAVs can complement each other to better and accomplish tasks such as logistics delivery, disaster area rescue, and target tracking.From an application perspective, UAVs and the joint delivery model of trucks and UAVs are already widely used in various fields. Firstly, in the agricultural sector, UAVs are mainly used for seed sowing and pollination, agricultural irrigation, and plant protection [3]. Torres et al. [4] conducted the first study of early weed management using UAVs. They pointed out that the number and resolution reflected in the images are a contradiction and the relationship between the two needs to be further optimized. Zhang et al. [5] studied the use of UAVs to apply pesticides to rice, which included reducing droplet floating, improving pesticide utilization, and increasing droplet deposition. Ayaz et al. [6] allowed the collaboration of UAVs with seeders to achieve more efficient seeding. Han et al. [7] gave a technical system for the application of UAVs in precision irrigation technology and suggested that, to meet the needs for efficient detection and precise dynamic management at different scales, UAVs should be combined with microsensing and ground monitoring systems. Secondly, in the field of rescue, Li et al. [8] proposed a new way of air-ground search and rescue with high altitude reconnaissance aircraft, groups of UAVs, and groups of unmanned vehicles for earthquake search and rescue scenarios. Zhang et al. [9] proposed a multi-UAV mission planning method for firefighting and rescue of multifire scenes. A multi-UAV mission planning model with changing target values over time is established to achieve a rational rescue according to the commander’s decision intent. Furthermore, the first issue that needs to be addressed when UAVs and vehicles work together on policing patrols is energy resupply. Kim [10] used multiple shared static charging stations at different geographical locations to solve the UAV energy constraint problem and established a path planning model based on MILP (mixed integer linear program) to find the optimal flight path for UAVs through genetic algorithms. Maini et al. [11] transformed collaborative air-ground coverage monitoring into a two-stage optimization problem and built a complex mixed integer linear programming model to optimize the path of UAV and sequence of refueling points. Hu et al. [12] established an air-ground collaborative patrol path planning model to optimize the UAVs’ patrol path and the unmanned vehicle energy resupply path. Finally, in the field of logistics distribution, Murray and Chu [13] proposed the joint delivery model of trucks and UAVs, where trucks carry UAVs from a distribution center to sequentially pass by some customer points where UAVs take off from the trucks to deliver packages for the customers in their vicinity. Ham [14] extended PDSTSP, considering the multitruck, multiwarehouse, and multi-UAV joint delivery that can be delivered and picked up by UAVs and using constraint planning solutions. Agatz et al. [15] modeled the travelling salesman problem with UAV (TSP-D), considered the same take-off and return positions of the UAV, and proposed a dynamic programming solution. Mario et al. [16] studied the TSP-D where the takeoff and return positions of the UAVs can be different and designed a greedy algorithm to solve the problem. Poikonen et al. [17] analyzed that the time for joint parallel delivery of trucks and UAVs is less than the delivery time of trucks alone in the worst case. Chu et al. [18] proposed a rural e-commerce logistics delivery model in which a soft time window and simultaneous pickup and delivery of trucks and UAVs were considered. With the goal of minimizing the total cost and using intelligent optimization algorithms, the total cost of terminal logistics is then significantly reduced compared to the delivery method using trucks alone. Han et al. [19] studied the delivery model of “vehicle + UAV” joint transportation of military materials in alpine mountain environment and wrote CTDEA algorithm to solve the problem. Among various application fields, logistics distribution is the most popular, which is also the main research field of this paper.The vehicle routing problem is an NP-hard problem [20]. The more complex problem of joint delivery model of trucks and UAVs is also an NP-hard problem. Modern heuristic algorithms are the main method for solving such problems. These include genetic algorithm (GA), simulated annealing (SA), artificial bee colony algorithm (ABC), neural network (NN), and ant colony algorithm (ACA). Different algorithms have different solving performances, and they are the most important methods for solving vehicle routing problems at present. William et al. [21] introduced genetic algorithms for the study of vehicle routing problem and to solve the VRPTW problem. Shim et al. [22] designed a hybrid genetic algorithm to solve the vehicle routing problem for multiple vehicle models in multiple warehouses. The simulated annealing algorithm was first applied to combinatorial optimization problems by Tarantilis et al. [23]. Osman et al. [24] used the simulated annealing algorithm to solve the vehicle routing problem effectively. Li et al. [25] designed a multistage solution of the hybrid variable neighbourhood artificial bee colony algorithm to solve the dynamic demand vehicle routing problem with continuously updated customer points. Pei and Yu [26] proposed an improved artificial bee colony algorithm based on probability matrix model and elite retention strategy for solving perishable product distribution routing optimization problems in logistics industry. Li et al. [27] combined the ant colony system (ACS) with the maximum and minimum ant system (MMAS) to design an improved ant colony algorithm to solve the vehicle routing problem with time windows. Aiming at the “last mile” problem of fresh produce delivery, Fu and Liu [28] constructed an open time-varying vehicle routing optimization model with the objective of minimizing the total delivery cost and designed an improved ant colony algorithm to solve the problem according to the characteristics of the model.Recently, in China, the e-commerce industry has been growing rapidly with the scale of online shopping users increasing gradually year by year. Data showed that, by December 2020, the scale of China’s online shopping users has reached 782 million, increasing 72.15 million from March 2020, accounting for 79.1% of the total Internet users. With the booming economy, the disposable income per capita increasing, the scale of online shopping expanding, and online retail increasing year by year, online retail sales grew from RMB 5,155.6 billion in 2016 to RMB 1,176.01 billion in 2020, with a compound annual growth rate of 22.89% and online sales are expected to reach RMB 1,375.93 billion in 2021 indicating that the e-commerce is growing at an incredible speed. E-commerce makes shopping more convenient for customers which is an essential factor that enables e-commerce to develop at a rapid pace. However, the key aspect of the development of e-commerce is the delivery of logistics. After placing orders, the top concerns for the customers are the delivery time and the integrity of the delivered goods, which means the distribution process fundamentally determines the service level of e-commerce. Therefore, it is crucial to optimize the delivery efficiency and deliver goods with integrity in time for customers, while optimizing routes and reducing distribution costs for logistics companies are the top priorities. Therefore, it is of great significance to study e-commerce logistics delivery patterns with the aim of minimizing total delivery cost and maximizing customer satisfaction.To sum up, the joint mode of trucks and UAVs is feasible. It has been widely used in agriculture, rescue, public security patrol, and logistics distribution, and the application of various modern heuristic algorithms in solving vehicle routing problems is discussed. This paper mainly studies the path optimization problem of the joint delivery mode of trucks and UAVs under the background of e-commerce. From the above analysis, it can be seen that the current researches mostly consider trucks carrying UAVs and UAVs can only serve one customer point and do not consider that UAVs will be limited by load capacity and mileage, resulting in some customer points not being able to get delivery services; also customer satisfaction was not taken into account. Therefore, in the joint delivery process of trucks and UAVs in this paper, the UAVs take off from the joint distribution transfer station to provide delivery services for nearby customer points, and, after completing the delivery task, they can return to other transfer stations that are closer. In addition, while trucks supply goods to be delivered at the joint distribution transfer station, they must also provide delivery services for those customer points that cannot be reached by UAVs due to UAV load capacity and mileage restrictions. Based on this, a mathematical model is established with the goal of minimizing total distribution cost and maximizing customer satisfaction, which is solved by the ABC-ACO algorithm. The results show that the joint delivery mode of trucks and UAVs has lower costs with higher customer satisfaction compared to trucks alone, and the improved ant colony algorithm is more efficient than the traditional ant colony algorithm.The major contributions of this study are as follows:(1)
This paper proposes and analyzes a joint delivery mode of trucks and UAVs which is different from the existing research.(2)
A joint delivery multiobjective optimization model is developed with the objectives of minimizing total delivery cost and maximizing customer satisfaction with delivery time and integrity of goods.(3)
To avoid prematurity, the classification idea of the artificial bee colony algorithm is introduced into the ant colony algorithm and the ant colony algorithm is improved. Limits are placed on the upper and lower limits of pheromone concentration to prevent the algorithm from stopping iterations after prematurity has occurred. Finally, the ABC-ACA is used to solve the model in this paper.Section2 describes the problem of joint delivery of trucks and UAVs and builds the mathematical model. Section 3 is dedicated to algorithm design. Section 4 is dedicated to calculation examples analysis and Section 5 gives a summary of this paper and prospects for future research.


## 2. Problem Description and Model Establishment

The traditional truck-alone delivery mode is shown in Figure1. In the traditional model, the truck departs from the distribution center carrying goods needed by several customer points, in order to serve each customer point in turn, and finally returns to the distribution center from which it departs. With the continuous development of urban e-commerce, the range of customers to be served is getting wider and wider, and how to achieve customer satisfaction in terms of time window and integrity of goods has gradually become the goal pursued by logistics enterprises. Presently, there are a series of problems in e-commerce distribution, such as urban traffic congestion, scattered customer points, and numerous distribution points with small delivery volume. These problems make the traditional delivery model of trucks not able to complete the delivery tasks efficiently. In order to make delivery more efficient, this paper proposes a joint delivery mode of trucks and UAVs based on the characteristics of UAVs with less affection by terrain, low delivery cost, and high distribution efficiency, which combines the advantages of trucks and UAVs to make delivery process more efficient and competitive for logistics companies.Figure 1
Traditional truck-alone delivery mode.


### 2.1. Problem Description

The joint delivery mode of trucks and UAVs is shown in Figure2. Joint distribution transfer stations are established near congestion-prone roads, and a certain number of UAVs are equipped in these transfer stations, which will deliver to customers near the transfer stations. Analogous to the two-level vehicle routing problem, the first-level distribution is the truck routing problem; that is, the truck departs from the distribution center, when the truck is loaded with goods for the customers near the joint distribution transfer station and goods for customer points beyond the UAV load or range, then the truck visits these transfer stations and customer points in turn and finally returns to the distribution center. Secondary distribution is a delivery mission for UAVs. Each UAV departs from a joint distribution transfer station and then provides delivery services to customer points near the transfer station which accord with the UAVs’ loading capacity and flight range. What needs to be emphasized is that, after the UAVs’ completion of the delivery tasks, they can return to the transfer stations from which they departed or other available transfer stations nearby.Figure 2
Joint distribution mode of trucks and UAVs.As the issue requires logistics companies to consider both minimizing delivery costs and maximizing customer satisfaction, this paper builds a multiobjective optimization model for joint delivery.Without losing generality, this paper makes the following assumptions:(1)
There is only one distribution center.(2)
Each customer point can only be served by one UAV or one truck, because each customer point can only be served once in real life.(3)
Distribution centers have multiple trucks of the same type and multiple UAVs of the same type in each joint distribution transfer station.(4)
The maximum payload and the longest flight distance of the UAV are known.(5)
Each UAV can load multiple packages at once. In other words, the UAV can serve multiple customers at a time. This assumption is reasonable based on real-life UAV delivery experience and the load of the UAVs.(6)
The UAV can continue delivery after battery replacement or charging at the joint delivery transfer station.(7)
UAV battery changes time and loading time at joint distribution transfer station are disregarded.(8)
The location coordinates of the distribution center, customers, and joint distribution transfer stations are known. These are known in the actual distribution process.(9)
The time windows of all customers are known.(10)
UAVs and trucks move at uniform speed.


### 2.2. Customer Satisfaction Function

#### 2.2.1. Time Satisfaction Function

Unlike considering soft time windows or hard time windows, in the actual delivery process, customers may prefer to get the delivery service at a specific time period within the time window, and earlier or later than this time period can lead to different degrees of dissatisfaction [29]. As a result, this paper blurs the time windows of each customer point. This fuzzy time window includes the time range in which the customer most wants to get the delivery service and the service time range that can be tolerated. Specifically, the level of satisfaction is 100% if the delivery service is received within the time range ei,li by consumer i. The time window within this time range is called the most satisfactory time window. Satisfaction would gradually decrease as the gap with the most satisfactory time window increases if the delivery service is received within the time ranges Ei,ei and Ei,ei by consumer i. The time window Ei,Li is called tolerable time window. Completely unsatisfied or satisfaction is 0 if the delivery service is received beyond the time range Ei,Li by consumer i. The time satisfaction function is shown in Figure 3.Figure 3
Time satisfaction function.The time satisfaction function can be expressed as follows:(1)fiti=ti−Eiei−Eiα,Ei<ti<ei,1,ei≤ti≤li,Li−tiLi−liβ,li<ti<Li,0,else,where ti is the time when the truck or UAV starts service for customer point i and α,β is the customer’s sensitivity factor for time.


#### 2.2.2. Goods Damage Satisfaction Function

Throughout the delivery process, the degree of damage to the goods after they are received by the customer affects customer satisfaction to some extent. E-commerce goods may be damaged to a certain extent in the process of distribution due to goods extrusion, improper operation of handling staff, or goods collision. Therefore, goods damage comes as another important issue for logistics enterprises to consider. There is a negative correlation between the goods damage rate and customer satisfaction: the higher the damage rate is, the lower the customer satisfaction is. This paper only considers the goods damage caused by the accumulation of transportation time during the transportation process. The goods damage rate can be calculated as follows:(2)yi=qti−t0,where yi is the damage rate of customer point i, t0 is the departure time from the distribution center or joint distribution transfer station, and q is the goods damage coefficient per unit time.The most satisfied or the satisfaction is 100% if the goods damage rate is within the range0,h by consumer i. Customer satisfaction decreases as the rate of cargo damage increases if the goods damage rate is within the range h,n by consumer i. When the damage rate exceeds n, the customer satisfaction is 0. Therefore, the damage satisfaction function is shown in Figure 4.Figure 4
Goods damage satisfaction function.The goods damage satisfaction function can be expressed as follows:(3)uiyi=0,yi>n,n−yin−h,h≤yi≤n,1,0≤yi<h.


### 2.3. Definition of Parameters and Variables

The joint delivery problem of trucks and UAVs can be defined on an undirected graphG=P,E,F, where P=P0∪PS∪PC is the set of points, P0 is distribution center, PS is the set of joint distribution transfer stations, PC=Pck∪Pcv is the set of customer points, Pck is the set of customer points that cannot be visited by UAV due to load and range restrictions and can only be served by trucks, Pcv is the set of customer points that are serviced by UAVs, and MS=PS∪Pcv is the set of customer points accessible by UAVs and joint distribution transfer stations. E=i,j|i,j∈P,i≠j is the set of trucks driving edges, and F=i,j|i,j∈MS,i≠j is the set of UAVs flighting edges.K: the set of trucks;V: the set of UAVs;QK: the maximum load of each truck;DV: the maximum flight distance of each UAV;qi: the demand of consumer i;Sv: the transfer station for the i-th UAV;WiSvv0≤WiSvv≤QV: the load capacity of UAV v taking off from station Sv when leaving customer point i;v: the truck speed;v′: the UAV speed;dij: the linear distance between nodes i and j;η: the multiple of the distance of the truck greater than the straight line distance;tik: the time when the truck karrives at node i;tiv: the time when the UAV varrives at node i;tki: the time for the truck to serve the customers;tvi: the time for the UAV to serve the customers;ei,li: the most satisfying time window of customer i;Ei,Li: the tolerable service time of customer i;fiti: the time satisfaction function;0,h: the range of damage rate acceptable to customers;h,n: the range of damage rate that customers can tolerate;uiyi: the function of satisfaction of goods damage;Cka: the fixed cost of single truck;Cva: the fixed cost of single UAV;Ckb: the transport cost per unit distance of the truck;Cvb: the flight cost per unit distance of the UAV;Pkn: the set of the n-th distribution routes of truck k, where Pkn⊆P,0≤n≤num1,num1=P; that is, num1 is the number of elements in P;Pvm: the set of the m-th distribution routes of UAV v, where Pvm⊆Pcv,0≤m≤num2,num2=Pcv; that is, num2 is the number of elements in Pcv;xijk=1,Truckkruns from nodeito nodej,0,else.;yijv=1,UAVvflights from nodeito nodej,0,else.;Pijk=1,In the path of truckK,nodeiprecedes nodejbut not necessarily continuous,0,else.


### 2.4. Mathematical Model

According to the above analysis, the total costZ1 is composed with the fixed cost and delivery cost of trucks and UAVs as follows:(4)Z1=Ca+Cb,where Ca is the total start-up cost of trucks and UAVs and Cb is the total delivery cost of trucks and UAVs. Since the start-up cost is related to the number of trucks and UAVs dispatched and the delivery cost is related to the moving distance of trucks and UAVs, Ca and Cb can be expressed as follows:(5)Ca=Cka∑j∈PS∪Pck∑k∈Kx0jk+Cva∑i∈PS∑j∈Pcv∑v∈Vyijv,(6)Cb=Ckb∑i,j∈P0∪PS∪Pck∑k∈K1+ηdijxijk+Cvb∑i,j∈PS∪Pcv∑v∈Vdijyijv.Based on the above description and hypotheses, the multiobjective optimization model for the joint delivery of trucks and UAVs can be established as follows:(7)minZ1=Ca+Cb,(8)minZ2=ω11−1N∑i∈PCfiti+ω21−1N∑i∈PCuiyi,(9)s.t.∑i∈P∑k∈Kxijk+∑i∈P∑v∈Vyijv=1,∀j∈Pcv,(10)∑i∈P∑j∈Pxijk≤K,∀k∈K,(11)∑i∈PS∪Pckxi0k=∑i∈PS∪Pckx0ik,∀k∈K,(12)∑i∈Pxijk=∑i∈Pxjik≤1,∀j∈P,∀k∈K,i≠j,(13)∑i∈P∑j∈Pxijkqi≤QK,∀k∈K,(14)∑i∈Pcvyijv=∑i∈Pcvyjiv≤1,∀j∈Pcv∪Sv,∀v∈V,(15)∑i∈P∑k∈Kxijk≤∑i∈P∑v∈Vyijv,∀j∈PS,(16)∑i∈P∑k∈Kxijk=1,∀j∈Pck,(17)∑i∈PS∪Pcvyijv=∑i∈PS∪Pcvyjiv=0,∀j∈Pck,∀v∈V,(18)dgi+∑i∈Pcv∑j∈Pcvdij+djg≤DV,∀g∈PS,(19)∑i∈Pcvygiv=0,∀g∈P0,∀v∈V,(20)∑i∈Pcvyigv=0,∀g∈P0,∀v∈V,(21)∑i∈PS∑j∈Pcvyijv=∑i∈Pcv∑j∈PSyijv,∀v∈V,(22)WSvSvv−qjySvjv−Qv1−ySvjv≤WjSvv≤WSvSvv−qjySvjv+Qv1−ySvjv,∀j∈Pcv,∀v∈V,(23)WiSvv−qjyijv−QV1−yijv≤WjSvv≤WiSvv−qjyijv+QV1−yijv,∀i∈Pcv,∀j∈Pcv,∀v∈V,(24)∑i∈Pkn∑j∈Pknxijk≤Pkn−1,∀k∈K,∀Pkn⊆P,0≤n≤num1,(25)∑i∈Pvm∑j∈Pvmyijv≤Pvm−1,∀v∈V,∀Pvm⊆Pcv,0≤m≤num2,(26)tjk=∑i,j∈P0∪PS∪Pcktik+dij1+ηv+tki,∀k∈K,(27)tjv=∑i,j∈PS∪Pcvtiv+dijv′+tvi,∀v∈V,where equations (7) and (8) are objective functions. Equation (7) implies the minimum total cost of delivery. Equation (8) implies that the average customer dissatisfaction is minimal. Equation (9) implies that any customer point can only be served once by an UAV or a truck. Equation (10) indicates the limit of the number of trucks used. Equation (11) indicates that the truck departs from the distribution center and returns to the distribution center after completing the delivery task. Equation (12) implies that the truck drives into a node and then drives out from this node. Equation (13) indicates that the good loaded by the truck cannot exceed its maximum load constraint. Equation (14) indicates that after the UAV flies into a certain customer point, it will fly out from the customer point. Equation (15) shows that the UAVs at the joint delivery transfer station can perform delivery services only after the trucks have visited the joint delivery transfer station. Equation (16) indicates customer points that cannot be visited by UAVs due to load and range restrictions and can only be served by trucks for delivery. Equation (17) indicates customer points that exceed the load and mileage constraints of the UAV and therefore cannot be accessed by the UAV. Equation (18) implies the flight distance constraint of the UAV. Equation (19) indicates that the UAV cannot be launched directly from the distribution center to the customer points. Equation (20) indicates that the UAV cannot fly directly from the customer point to the distribution center. Equation (21) indicates that the UAV departs from a joint distribution transfer station and can return to any transfer station after completing its delivery task. Equation (22) represents the load capacity of the UAV from the joint delivery transfer station to the customer point j after the delivery is completed. Equation (23) represents the load capacity of the UAV from customer point i to customer point j after completing this delivery task. Equation (24) is the detrucking branch constraint, which is the removal of incomplete routes from the truck routes. Equation (25) is the de-UAV branch constraint, which is the removal of incomplete routes from the UAV routes. Equation (26) indicates the time when truck k arrives at node j. Equation (27) represents the time when the UAV v arrives at node j.In this paper, a multiobjective optimization model is established. In order to make the solution more convenient, the two objective functions are transformed into a single-objective optimization model by assigning weights. The transformed objective function can be expressed as follows:(28)minZ=ω1Ca+Cb+ω21−1N∑i∈PCfiti+ω31−1N∑i∈PCuiyi.


## 2.1. Problem Description

The joint delivery mode of trucks and UAVs is shown in Figure2. Joint distribution transfer stations are established near congestion-prone roads, and a certain number of UAVs are equipped in these transfer stations, which will deliver to customers near the transfer stations. Analogous to the two-level vehicle routing problem, the first-level distribution is the truck routing problem; that is, the truck departs from the distribution center, when the truck is loaded with goods for the customers near the joint distribution transfer station and goods for customer points beyond the UAV load or range, then the truck visits these transfer stations and customer points in turn and finally returns to the distribution center. Secondary distribution is a delivery mission for UAVs. Each UAV departs from a joint distribution transfer station and then provides delivery services to customer points near the transfer station which accord with the UAVs’ loading capacity and flight range. What needs to be emphasized is that, after the UAVs’ completion of the delivery tasks, they can return to the transfer stations from which they departed or other available transfer stations nearby.Figure 2
Joint distribution mode of trucks and UAVs.As the issue requires logistics companies to consider both minimizing delivery costs and maximizing customer satisfaction, this paper builds a multiobjective optimization model for joint delivery.Without losing generality, this paper makes the following assumptions:(1)
There is only one distribution center.(2)
Each customer point can only be served by one UAV or one truck, because each customer point can only be served once in real life.(3)
Distribution centers have multiple trucks of the same type and multiple UAVs of the same type in each joint distribution transfer station.(4)
The maximum payload and the longest flight distance of the UAV are known.(5)
Each UAV can load multiple packages at once. In other words, the UAV can serve multiple customers at a time. This assumption is reasonable based on real-life UAV delivery experience and the load of the UAVs.(6)
The UAV can continue delivery after battery replacement or charging at the joint delivery transfer station.(7)
UAV battery changes time and loading time at joint distribution transfer station are disregarded.(8)
The location coordinates of the distribution center, customers, and joint distribution transfer stations are known. These are known in the actual distribution process.(9)
The time windows of all customers are known.(10)
UAVs and trucks move at uniform speed.


## 2.2. Customer Satisfaction Function

### 2.2.1. Time Satisfaction Function

Unlike considering soft time windows or hard time windows, in the actual delivery process, customers may prefer to get the delivery service at a specific time period within the time window, and earlier or later than this time period can lead to different degrees of dissatisfaction [29]. As a result, this paper blurs the time windows of each customer point. This fuzzy time window includes the time range in which the customer most wants to get the delivery service and the service time range that can be tolerated. Specifically, the level of satisfaction is 100% if the delivery service is received within the time range ei,li by consumer i. The time window within this time range is called the most satisfactory time window. Satisfaction would gradually decrease as the gap with the most satisfactory time window increases if the delivery service is received within the time ranges Ei,ei and Ei,ei by consumer i. The time window Ei,Li is called tolerable time window. Completely unsatisfied or satisfaction is 0 if the delivery service is received beyond the time range Ei,Li by consumer i. The time satisfaction function is shown in Figure 3.Figure 3
Time satisfaction function.The time satisfaction function can be expressed as follows:(1)fiti=ti−Eiei−Eiα,Ei<ti<ei,1,ei≤ti≤li,Li−tiLi−liβ,li<ti<Li,0,else,where ti is the time when the truck or UAV starts service for customer point i and α,β is the customer’s sensitivity factor for time.


### 2.2.2. Goods Damage Satisfaction Function

Throughout the delivery process, the degree of damage to the goods after they are received by the customer affects customer satisfaction to some extent. E-commerce goods may be damaged to a certain extent in the process of distribution due to goods extrusion, improper operation of handling staff, or goods collision. Therefore, goods damage comes as another important issue for logistics enterprises to consider. There is a negative correlation between the goods damage rate and customer satisfaction: the higher the damage rate is, the lower the customer satisfaction is. This paper only considers the goods damage caused by the accumulation of transportation time during the transportation process. The goods damage rate can be calculated as follows:(2)yi=qti−t0,where yi is the damage rate of customer point i, t0 is the departure time from the distribution center or joint distribution transfer station, and q is the goods damage coefficient per unit time.The most satisfied or the satisfaction is 100% if the goods damage rate is within the range0,h by consumer i. Customer satisfaction decreases as the rate of cargo damage increases if the goods damage rate is within the range h,n by consumer i. When the damage rate exceeds n, the customer satisfaction is 0. Therefore, the damage satisfaction function is shown in Figure 4.Figure 4
Goods damage satisfaction function.The goods damage satisfaction function can be expressed as follows:(3)uiyi=0,yi>n,n−yin−h,h≤yi≤n,1,0≤yi<h.


## 2.2.1. Time Satisfaction Function

Unlike considering soft time windows or hard time windows, in the actual delivery process, customers may prefer to get the delivery service at a specific time period within the time window, and earlier or later than this time period can lead to different degrees of dissatisfaction [29]. As a result, this paper blurs the time windows of each customer point. This fuzzy time window includes the time range in which the customer most wants to get the delivery service and the service time range that can be tolerated. Specifically, the level of satisfaction is 100% if the delivery service is received within the time range ei,li by consumer i. The time window within this time range is called the most satisfactory time window. Satisfaction would gradually decrease as the gap with the most satisfactory time window increases if the delivery service is received within the time ranges Ei,ei and Ei,ei by consumer i. The time window Ei,Li is called tolerable time window. Completely unsatisfied or satisfaction is 0 if the delivery service is received beyond the time range Ei,Li by consumer i. The time satisfaction function is shown in Figure 3.Figure 3
Time satisfaction function.The time satisfaction function can be expressed as follows:(1)fiti=ti−Eiei−Eiα,Ei<ti<ei,1,ei≤ti≤li,Li−tiLi−liβ,li<ti<Li,0,else,where ti is the time when the truck or UAV starts service for customer point i and α,β is the customer’s sensitivity factor for time.


## 2.2.2. Goods Damage Satisfaction Function

Throughout the delivery process, the degree of damage to the goods after they are received by the customer affects customer satisfaction to some extent. E-commerce goods may be damaged to a certain extent in the process of distribution due to goods extrusion, improper operation of handling staff, or goods collision. Therefore, goods damage comes as another important issue for logistics enterprises to consider. There is a negative correlation between the goods damage rate and customer satisfaction: the higher the damage rate is, the lower the customer satisfaction is. This paper only considers the goods damage caused by the accumulation of transportation time during the transportation process. The goods damage rate can be calculated as follows:(2)yi=qti−t0,where yi is the damage rate of customer point i, t0 is the departure time from the distribution center or joint distribution transfer station, and q is the goods damage coefficient per unit time.The most satisfied or the satisfaction is 100% if the goods damage rate is within the range0,h by consumer i. Customer satisfaction decreases as the rate of cargo damage increases if the goods damage rate is within the range h,n by consumer i. When the damage rate exceeds n, the customer satisfaction is 0. Therefore, the damage satisfaction function is shown in Figure 4.Figure 4
Goods damage satisfaction function.The goods damage satisfaction function can be expressed as follows:(3)uiyi=0,yi>n,n−yin−h,h≤yi≤n,1,0≤yi<h.


## 2.3. Definition of Parameters and Variables

The joint delivery problem of trucks and UAVs can be defined on an undirected graphG=P,E,F, where P=P0∪PS∪PC is the set of points, P0 is distribution center, PS is the set of joint distribution transfer stations, PC=Pck∪Pcv is the set of customer points, Pck is the set of customer points that cannot be visited by UAV due to load and range restrictions and can only be served by trucks, Pcv is the set of customer points that are serviced by UAVs, and MS=PS∪Pcv is the set of customer points accessible by UAVs and joint distribution transfer stations. E=i,j|i,j∈P,i≠j is the set of trucks driving edges, and F=i,j|i,j∈MS,i≠j is the set of UAVs flighting edges.K: the set of trucks;V: the set of UAVs;QK: the maximum load of each truck;DV: the maximum flight distance of each UAV;qi: the demand of consumer i;Sv: the transfer station for the i-th UAV;WiSvv0≤WiSvv≤QV: the load capacity of UAV v taking off from station Sv when leaving customer point i;v: the truck speed;v′: the UAV speed;dij: the linear distance between nodes i and j;η: the multiple of the distance of the truck greater than the straight line distance;tik: the time when the truck karrives at node i;tiv: the time when the UAV varrives at node i;tki: the time for the truck to serve the customers;tvi: the time for the UAV to serve the customers;ei,li: the most satisfying time window of customer i;Ei,Li: the tolerable service time of customer i;fiti: the time satisfaction function;0,h: the range of damage rate acceptable to customers;h,n: the range of damage rate that customers can tolerate;uiyi: the function of satisfaction of goods damage;Cka: the fixed cost of single truck;Cva: the fixed cost of single UAV;Ckb: the transport cost per unit distance of the truck;Cvb: the flight cost per unit distance of the UAV;Pkn: the set of the n-th distribution routes of truck k, where Pkn⊆P,0≤n≤num1,num1=P; that is, num1 is the number of elements in P;Pvm: the set of the m-th distribution routes of UAV v, where Pvm⊆Pcv,0≤m≤num2,num2=Pcv; that is, num2 is the number of elements in Pcv;xijk=1,Truckkruns from nodeito nodej,0,else.;yijv=1,UAVvflights from nodeito nodej,0,else.;Pijk=1,In the path of truckK,nodeiprecedes nodejbut not necessarily continuous,0,else.


## 2.4. Mathematical Model

According to the above analysis, the total costZ1 is composed with the fixed cost and delivery cost of trucks and UAVs as follows:(4)Z1=Ca+Cb,where Ca is the total start-up cost of trucks and UAVs and Cb is the total delivery cost of trucks and UAVs. Since the start-up cost is related to the number of trucks and UAVs dispatched and the delivery cost is related to the moving distance of trucks and UAVs, Ca and Cb can be expressed as follows:(5)Ca=Cka∑j∈PS∪Pck∑k∈Kx0jk+Cva∑i∈PS∑j∈Pcv∑v∈Vyijv,(6)Cb=Ckb∑i,j∈P0∪PS∪Pck∑k∈K1+ηdijxijk+Cvb∑i,j∈PS∪Pcv∑v∈Vdijyijv.Based on the above description and hypotheses, the multiobjective optimization model for the joint delivery of trucks and UAVs can be established as follows:(7)minZ1=Ca+Cb,(8)minZ2=ω11−1N∑i∈PCfiti+ω21−1N∑i∈PCuiyi,(9)s.t.∑i∈P∑k∈Kxijk+∑i∈P∑v∈Vyijv=1,∀j∈Pcv,(10)∑i∈P∑j∈Pxijk≤K,∀k∈K,(11)∑i∈PS∪Pckxi0k=∑i∈PS∪Pckx0ik,∀k∈K,(12)∑i∈Pxijk=∑i∈Pxjik≤1,∀j∈P,∀k∈K,i≠j,(13)∑i∈P∑j∈Pxijkqi≤QK,∀k∈K,(14)∑i∈Pcvyijv=∑i∈Pcvyjiv≤1,∀j∈Pcv∪Sv,∀v∈V,(15)∑i∈P∑k∈Kxijk≤∑i∈P∑v∈Vyijv,∀j∈PS,(16)∑i∈P∑k∈Kxijk=1,∀j∈Pck,(17)∑i∈PS∪Pcvyijv=∑i∈PS∪Pcvyjiv=0,∀j∈Pck,∀v∈V,(18)dgi+∑i∈Pcv∑j∈Pcvdij+djg≤DV,∀g∈PS,(19)∑i∈Pcvygiv=0,∀g∈P0,∀v∈V,(20)∑i∈Pcvyigv=0,∀g∈P0,∀v∈V,(21)∑i∈PS∑j∈Pcvyijv=∑i∈Pcv∑j∈PSyijv,∀v∈V,(22)WSvSvv−qjySvjv−Qv1−ySvjv≤WjSvv≤WSvSvv−qjySvjv+Qv1−ySvjv,∀j∈Pcv,∀v∈V,(23)WiSvv−qjyijv−QV1−yijv≤WjSvv≤WiSvv−qjyijv+QV1−yijv,∀i∈Pcv,∀j∈Pcv,∀v∈V,(24)∑i∈Pkn∑j∈Pknxijk≤Pkn−1,∀k∈K,∀Pkn⊆P,0≤n≤num1,(25)∑i∈Pvm∑j∈Pvmyijv≤Pvm−1,∀v∈V,∀Pvm⊆Pcv,0≤m≤num2,(26)tjk=∑i,j∈P0∪PS∪Pcktik+dij1+ηv+tki,∀k∈K,(27)tjv=∑i,j∈PS∪Pcvtiv+dijv′+tvi,∀v∈V,where equations (7) and (8) are objective functions. Equation (7) implies the minimum total cost of delivery. Equation (8) implies that the average customer dissatisfaction is minimal. Equation (9) implies that any customer point can only be served once by an UAV or a truck. Equation (10) indicates the limit of the number of trucks used. Equation (11) indicates that the truck departs from the distribution center and returns to the distribution center after completing the delivery task. Equation (12) implies that the truck drives into a node and then drives out from this node. Equation (13) indicates that the good loaded by the truck cannot exceed its maximum load constraint. Equation (14) indicates that after the UAV flies into a certain customer point, it will fly out from the customer point. Equation (15) shows that the UAVs at the joint delivery transfer station can perform delivery services only after the trucks have visited the joint delivery transfer station. Equation (16) indicates customer points that cannot be visited by UAVs due to load and range restrictions and can only be served by trucks for delivery. Equation (17) indicates customer points that exceed the load and mileage constraints of the UAV and therefore cannot be accessed by the UAV. Equation (18) implies the flight distance constraint of the UAV. Equation (19) indicates that the UAV cannot be launched directly from the distribution center to the customer points. Equation (20) indicates that the UAV cannot fly directly from the customer point to the distribution center. Equation (21) indicates that the UAV departs from a joint distribution transfer station and can return to any transfer station after completing its delivery task. Equation (22) represents the load capacity of the UAV from the joint delivery transfer station to the customer point j after the delivery is completed. Equation (23) represents the load capacity of the UAV from customer point i to customer point j after completing this delivery task. Equation (24) is the detrucking branch constraint, which is the removal of incomplete routes from the truck routes. Equation (25) is the de-UAV branch constraint, which is the removal of incomplete routes from the UAV routes. Equation (26) indicates the time when truck k arrives at node j. Equation (27) represents the time when the UAV v arrives at node j.In this paper, a multiobjective optimization model is established. In order to make the solution more convenient, the two objective functions are transformed into a single-objective optimization model by assigning weights. The transformed objective function can be expressed as follows:(28)minZ=ω1Ca+Cb+ω21−1N∑i∈PCfiti+ω31−1N∑i∈PCuiyi.


## 3. Algorithm Design

This paper studies the multiobjective optimization problem, which belongs to the NP-hard problem. When solving such problems, heuristic algorithms have been widely used [30]. This paper presents the joint delivery model of trucks and UAVs as a two-level path planning problem that requires a heuristic algorithm with parallel computing mechanisms to solve, and, due to the complexity of the problem, sufficient stability needs to be maintained in the solution process. The ant colony algorithm uses a distributed parallel computer system, which has the advantages of positive feedback and good robustness and can get a more satisfactory feasible solution within an acceptable time range. However, the ant colony algorithm tends to be premature and inefficient in the solving process [31]. Therefore, in this paper, the ant colony algorithm is improved by combining the idea of artificial bee colony algorithm, and the upper and lower limits of the global pheromone concentration are given to prevent the algorithm from affecting the optimization effect due to prematurity.


### 3.1. Principle of Ant Colony Algorithm

Ant colony algorithm (ACA) was first proposed by Italian scholar Dorigo and colleagues [32] in the 1990s. They found that single ant behaved simply when foraging, while ants exhibited an intelligent behavior when they foraged in groups. For example, the ant colony will search for the shortest path for food, because the ants in the ant colony will transmit information to each other through an information mechanism. After further research, it was found that ants would release “pheromone” on the path they passed during the foraging process. Ants within a colony have the ability to perceive “pheromones” and will follow paths with high concentrations of “pheromones.” Besides, each ant will leave “pheromones” on the path it passes. This is known as a positive feedback mechanism. It is because of such a process that the entire colony will follow the shortest path to the food source.


### 3.2. Principle of Artificial Bee Colony Algorithm

The artificial bee colony (ABC) algorithm was proposed by the group of Karaboga and Basturk [33] in 2005. It is an algorithm inspired by the behavior of bee colonies. The artificial bee colony algorithm imitates the process of honey collection by bees. This algorithm divides all bees into leading bees, detecting bees, and following bees, and these bees can complete their missions in the process of finding the optimal honey source [34]. In the process of solving the artificial bee colony algorithm, firstly leading bees look for nectar sources based on existing information and tell onlooker bees about the sources they have found. Following bees then select a nectar source based on the information obtained with a certain probability and find a candidate nectar source to compare with the previous one. Finally, when a nectar source is not renewed after a finite number of cycles, the bees associated with that source are transformed into leading bees to continue the search for potential new nectar sources.


### 3.3. Algorithm Improvement

Based on the ACA, the classification idea of ABC algorithm is introduced to dynamically divide the ant colony into two types, leading ants and detecting ants, according to the fitness value. Among them, leading ants search for a better path, and detecting ants search for other paths and more feasible solutions. Secondly, the weighting coefficients and fitness values are used to dynamically update the local pheromone concentrations. Finally, the pheromone concentration on each path was limited toτmin,τmax in order to prevent all ants from rapidly aggregating and stalling the search with too high a pheromone concentration on a particular path.


#### 3.3.1. Ant Colony Classification

Combining the classification idea of artificial bee colony algorithm, the dynamic classification operation is introduced on the basis of ant colony algorithm. The purpose is to divide the entire ant colony into two ant forms, leading ants and detecting ants, and search in parallel. The specific operation is to divide the ant colony into leading ants and detecting ants according to the different pheromone concentrations of the paths taken by different ants. Leading ants are responsible for searching for a better path, highlighting the pheromone concentration on this path, which speeds up the convergence of the algorithm. Detecting ants are responsible for searching for feasible solutions with better quality in addition to these better paths. This operation ensures the diversity of the algorithm, so that it will not fall into a local optimum and at the same time improve the quality of the solution.The ant colony classification formula can be expressed as follows:(29)fi=1Zi,(30)Ri=detecting ant,0<fi≤M,leading ant,M<fi≤1.In equation (29), Zi is the objective function of the model, and fi is the fitness of each ant, which is the reciprocal of the objective function. According to the different fitness value fi of each ant, the ant colony was divided into two types: detecting ant and leading ant. It can be expressed as equation (30), where M is the classification boundary point that divides ants into two classes 0<M<1: when 0<fi≤M, it is the detection ant; when M<fi≤1, it is the leading ant.


#### 3.3.2. Dynamic Updating of Local Pheromone

In order to better maintain the diversity of the population and improve the convergence speed of the algorithm, the weighted coefficient and fitness value are introduced to update the local pheromone [35], so that different types of ants can implement different local pheromone update strategies. They can be expressed as follows:(31)τijt+1=1−ρτijt+ρτij,(32)τij=λ1fi,(33)τij=λ2fi,where λ1 and λ2 are weighting coefficients, fi is the fitness of the i-th ant, and ρ is the rate of pheromone volatilization. Equation (32) is the local pheromone update formula of leading ants. Equation (33) is the local pheromone update formula of detecting ants. Two kinds of ants perform different updating strategies of dynamic pheromone, and λ1>λ2, to shorten the optimization time by highlighting the pheromone concentration on the optimal solution path.


#### 3.3.3. Pheromone Concentration Limit

In order to avoid prematurity and stagnant phenomena, the pheromone concentration on each path is controlled withinτmin,τmax. The pheromone less than τmin is assigned as τmin, and the pheromone greater than τmax is assigned as τmax. The purpose of this method is to avoid the fact that the pheromone concentration is too high to iterate, which will attract most ants to gather quickly and lead to premature phenomenon. The value formulas of pheromone upper and lower limits can be expressed as follows:(34)τmaxt=121−ρCt+σCt,(35)τmint=τmaxt20,where ρ is the pheromone volatilization rate, Ct is the optimal objective function in the t-th iteration, and σ is the number of optimal solutions of the t-th iteration.


### 3.4. Algorithm Steps

Step 1.
Initialize parameters.Step 2.
Create a tabu list and putm ants in the distribution center.Step 3.
Provided that the constraints are satisfied, each ant calculates the transfer probability according to equation (36) and selects the next visited node according to the transfer probability. In this equation, α is the relative importance factor of pheromone concentration, and β is the importance factor of heuristic function, which reflects the importance of ant to heuristic information. Jki is the set of cities that ant k is allowed to visit in the next step.(36)Pijk=τijαt1/Ziβt∑j∈Jkiτijαt1/Ziβt,j∈Jki,0,else.Step 4.
According to the transition probability, roulette is used to select the next node to visit.Step 5.
According to the ant colony classification, the fitness value is calculated and the ants are classified.Step 6.
Update the pheromone of leading ant and detecting ant.Step 7.
Exchange high-quality solution. IfZdetecting ants<Zleading ants, let two kinds of ants exchange high-quality solutions. This step is done by swapping the identity functions of the two types of ants, with the better detecting ant transforming into the new leading ant and the replaced leading ant converting into a detecting ant and performing the functions of a detecting ant. If the solution of the detecting ant is not better than the solution of the leading ant during the iteration, which means the algorithm does not perform a high-quality solution exchange, then proceed directly to Step 8.Step 8.
Update global pheromone. It is limited toτmin,τmax.Step 9.
Judge whether the end condition is satisfied at this time. If not, go to Step3 and start a new cycle. Otherwise, go to Step 10.Step 10.
If the maximum number of iterations is reached, the iteration is terminated.
The flow-process diagram of ABC-ACA is shown in Figure5.Figure 5
ABC-ACA flow chart.


## 3.1. Principle of Ant Colony Algorithm

Ant colony algorithm (ACA) was first proposed by Italian scholar Dorigo and colleagues [32] in the 1990s. They found that single ant behaved simply when foraging, while ants exhibited an intelligent behavior when they foraged in groups. For example, the ant colony will search for the shortest path for food, because the ants in the ant colony will transmit information to each other through an information mechanism. After further research, it was found that ants would release “pheromone” on the path they passed during the foraging process. Ants within a colony have the ability to perceive “pheromones” and will follow paths with high concentrations of “pheromones.” Besides, each ant will leave “pheromones” on the path it passes. This is known as a positive feedback mechanism. It is because of such a process that the entire colony will follow the shortest path to the food source.


## 3.2. Principle of Artificial Bee Colony Algorithm

The artificial bee colony (ABC) algorithm was proposed by the group of Karaboga and Basturk [33] in 2005. It is an algorithm inspired by the behavior of bee colonies. The artificial bee colony algorithm imitates the process of honey collection by bees. This algorithm divides all bees into leading bees, detecting bees, and following bees, and these bees can complete their missions in the process of finding the optimal honey source [34]. In the process of solving the artificial bee colony algorithm, firstly leading bees look for nectar sources based on existing information and tell onlooker bees about the sources they have found. Following bees then select a nectar source based on the information obtained with a certain probability and find a candidate nectar source to compare with the previous one. Finally, when a nectar source is not renewed after a finite number of cycles, the bees associated with that source are transformed into leading bees to continue the search for potential new nectar sources.


## 3.3. Algorithm Improvement

Based on the ACA, the classification idea of ABC algorithm is introduced to dynamically divide the ant colony into two types, leading ants and detecting ants, according to the fitness value. Among them, leading ants search for a better path, and detecting ants search for other paths and more feasible solutions. Secondly, the weighting coefficients and fitness values are used to dynamically update the local pheromone concentrations. Finally, the pheromone concentration on each path was limited toτmin,τmax in order to prevent all ants from rapidly aggregating and stalling the search with too high a pheromone concentration on a particular path.


### 3.3.1. Ant Colony Classification

Combining the classification idea of artificial bee colony algorithm, the dynamic classification operation is introduced on the basis of ant colony algorithm. The purpose is to divide the entire ant colony into two ant forms, leading ants and detecting ants, and search in parallel. The specific operation is to divide the ant colony into leading ants and detecting ants according to the different pheromone concentrations of the paths taken by different ants. Leading ants are responsible for searching for a better path, highlighting the pheromone concentration on this path, which speeds up the convergence of the algorithm. Detecting ants are responsible for searching for feasible solutions with better quality in addition to these better paths. This operation ensures the diversity of the algorithm, so that it will not fall into a local optimum and at the same time improve the quality of the solution.The ant colony classification formula can be expressed as follows:(29)fi=1Zi,(30)Ri=detecting ant,0<fi≤M,leading ant,M<fi≤1.In equation (29), Zi is the objective function of the model, and fi is the fitness of each ant, which is the reciprocal of the objective function. According to the different fitness value fi of each ant, the ant colony was divided into two types: detecting ant and leading ant. It can be expressed as equation (30), where M is the classification boundary point that divides ants into two classes 0<M<1: when 0<fi≤M, it is the detection ant; when M<fi≤1, it is the leading ant.


### 3.3.2. Dynamic Updating of Local Pheromone

In order to better maintain the diversity of the population and improve the convergence speed of the algorithm, the weighted coefficient and fitness value are introduced to update the local pheromone [35], so that different types of ants can implement different local pheromone update strategies. They can be expressed as follows:(31)τijt+1=1−ρτijt+ρτij,(32)τij=λ1fi,(33)τij=λ2fi,where λ1 and λ2 are weighting coefficients, fi is the fitness of the i-th ant, and ρ is the rate of pheromone volatilization. Equation (32) is the local pheromone update formula of leading ants. Equation (33) is the local pheromone update formula of detecting ants. Two kinds of ants perform different updating strategies of dynamic pheromone, and λ1>λ2, to shorten the optimization time by highlighting the pheromone concentration on the optimal solution path.


### 3.3.3. Pheromone Concentration Limit

In order to avoid prematurity and stagnant phenomena, the pheromone concentration on each path is controlled withinτmin,τmax. The pheromone less than τmin is assigned as τmin, and the pheromone greater than τmax is assigned as τmax. The purpose of this method is to avoid the fact that the pheromone concentration is too high to iterate, which will attract most ants to gather quickly and lead to premature phenomenon. The value formulas of pheromone upper and lower limits can be expressed as follows:(34)τmaxt=121−ρCt+σCt,(35)τmint=τmaxt20,where ρ is the pheromone volatilization rate, Ct is the optimal objective function in the t-th iteration, and σ is the number of optimal solutions of the t-th iteration.


## 3.3.1. Ant Colony Classification

Combining the classification idea of artificial bee colony algorithm, the dynamic classification operation is introduced on the basis of ant colony algorithm. The purpose is to divide the entire ant colony into two ant forms, leading ants and detecting ants, and search in parallel. The specific operation is to divide the ant colony into leading ants and detecting ants according to the different pheromone concentrations of the paths taken by different ants. Leading ants are responsible for searching for a better path, highlighting the pheromone concentration on this path, which speeds up the convergence of the algorithm. Detecting ants are responsible for searching for feasible solutions with better quality in addition to these better paths. This operation ensures the diversity of the algorithm, so that it will not fall into a local optimum and at the same time improve the quality of the solution.The ant colony classification formula can be expressed as follows:(29)fi=1Zi,(30)Ri=detecting ant,0<fi≤M,leading ant,M<fi≤1.In equation (29), Zi is the objective function of the model, and fi is the fitness of each ant, which is the reciprocal of the objective function. According to the different fitness value fi of each ant, the ant colony was divided into two types: detecting ant and leading ant. It can be expressed as equation (30), where M is the classification boundary point that divides ants into two classes 0<M<1: when 0<fi≤M, it is the detection ant; when M<fi≤1, it is the leading ant.


## 3.3.2. Dynamic Updating of Local Pheromone

In order to better maintain the diversity of the population and improve the convergence speed of the algorithm, the weighted coefficient and fitness value are introduced to update the local pheromone [35], so that different types of ants can implement different local pheromone update strategies. They can be expressed as follows:(31)τijt+1=1−ρτijt+ρτij,(32)τij=λ1fi,(33)τij=λ2fi,where λ1 and λ2 are weighting coefficients, fi is the fitness of the i-th ant, and ρ is the rate of pheromone volatilization. Equation (32) is the local pheromone update formula of leading ants. Equation (33) is the local pheromone update formula of detecting ants. Two kinds of ants perform different updating strategies of dynamic pheromone, and λ1>λ2, to shorten the optimization time by highlighting the pheromone concentration on the optimal solution path.


## 3.3.3. Pheromone Concentration Limit

In order to avoid prematurity and stagnant phenomena, the pheromone concentration on each path is controlled withinτmin,τmax. The pheromone less than τmin is assigned as τmin, and the pheromone greater than τmax is assigned as τmax. The purpose of this method is to avoid the fact that the pheromone concentration is too high to iterate, which will attract most ants to gather quickly and lead to premature phenomenon. The value formulas of pheromone upper and lower limits can be expressed as follows:(34)τmaxt=121−ρCt+σCt,(35)τmint=τmaxt20,where ρ is the pheromone volatilization rate, Ct is the optimal objective function in the t-th iteration, and σ is the number of optimal solutions of the t-th iteration.


## 3.4. Algorithm Steps

Step 1.
Initialize parameters.Step 2.
Create a tabu list and putm ants in the distribution center.Step 3.
Provided that the constraints are satisfied, each ant calculates the transfer probability according to equation (36) and selects the next visited node according to the transfer probability. In this equation, α is the relative importance factor of pheromone concentration, and β is the importance factor of heuristic function, which reflects the importance of ant to heuristic information. Jki is the set of cities that ant k is allowed to visit in the next step.(36)Pijk=τijαt1/Ziβt∑j∈Jkiτijαt1/Ziβt,j∈Jki,0,else.Step 4.
According to the transition probability, roulette is used to select the next node to visit.Step 5.
According to the ant colony classification, the fitness value is calculated and the ants are classified.Step 6.
Update the pheromone of leading ant and detecting ant.Step 7.
Exchange high-quality solution. IfZdetecting ants<Zleading ants, let two kinds of ants exchange high-quality solutions. This step is done by swapping the identity functions of the two types of ants, with the better detecting ant transforming into the new leading ant and the replaced leading ant converting into a detecting ant and performing the functions of a detecting ant. If the solution of the detecting ant is not better than the solution of the leading ant during the iteration, which means the algorithm does not perform a high-quality solution exchange, then proceed directly to Step 8.Step 8.
Update global pheromone. It is limited toτmin,τmax.Step 9.
Judge whether the end condition is satisfied at this time. If not, go to Step3 and start a new cycle. Otherwise, go to Step 10.Step 10.
If the maximum number of iterations is reached, the iteration is terminated.
The flow-process diagram of ABC-ACA is shown in Figure5.Figure 5
ABC-ACA flow chart.


## 4. Analysis of Calculation Examples

### 4.1. Background Analysis and Parameter Setting

This paper takes the order of a distribution center of an e-commerce logistics enterprise in city A as the customer sample. The ABC-ACO algorithm is used to plan the joint delivery of trucks and UAVs, so as to minimize the delivery cost and maximize customer satisfaction under the above constraints. The location coordinates of 15 customer points, 1 distribution center, and 5 joint distribution transfer stations, the time window requirements of customer points, and the requirement and service time of each customer point are shown in Table1.Table 1
Information table of each node.
No.NodePosition coordinates (X,Y)Demandsqi/kgTime windowsei/hli/hEi/hLi/h0Distribution center(94,100)07207201Customer point 1(60,135)410117122Customer point 2(40,36)17811.57.512.53Customer point 3(48,96)3812712.54Customer point 4(92,154)258.513813.55Customer point 5(97,50)10101611176Customer point 6(120,90)11913.58167Customer point 7(44,160)229.514914.58Customer point 8(20,54)209.515915.59Customer point 9(108,32)5101691710Customer point 10(130,88)51116.5101711Customer point 11(56,100)511.5171117.512Customer point 12(50,68)61017.59.51813Customer point 13(43,110)181315101614Customer point 14(135,24)311719159.515Customer point 15(23,108)810199.520AJoint distribution transfer station A(124,103)0720720BJoint distribution transfer station B(52,120)0720720CJoint distribution transfer station C(30,114)0720720DJoint distribution transfer station D(50,50)0720720EJoint distribution transfer station E(105,43)0720720The distance between nodes is measured by vector distance, which can be expressed by the following equation:(37)dij=xi−xj2+yi−yj21/2The relevant parameters of trucks and UAVs are shown in Table2.Table 2
Description of relevant parameters.
Related parametersTrucks in distribution centersUAVs in joint distribution transfer stationsQuantity (vehicle, frame)510Maximum load (kg)10020Maximum transport distance (km)—30Speed (km/h)3080Transportation cost per unit distance (yuan/km)51Start-up cost (yuan/time)10020Service hours (h)0.50.5In addition, the multiple of the distance of the truck greater than the straight distanceη=0.3, time sensitivity coefficient α=0.5,β=0.8, goods damage coefficient q=0.1%, the range of goods damage rate acceptable to customers is 0,0.2%, the range of goods damage rate tolerable to customers is 0.2%,1, and the weight of objective function is ω1=0.5,ω2=0.3,ω3=0.2.


### 4.2. Result Analysis

According to the ABC-ACA described above, using MATLAB software, the joint delivery model of trucks and UAVs is solved. Through multiple simulations of the example, the parameters are set as follows:α=1, β=3, ρ=0.4, Ant_num=20, M=0.7, λ1=4, and λ2=2.Figure6 shows the route map of the optimal delivery scheme for the joint delivery model of trucks and UAVs by using ABC-ACA.Figure 6
The optimal delivery scheme for joint delivery of trucks and UAVs by using ABC-ACA.Figure7 shows the optimal delivery scheme when only trucks are used for delivery by using ABC-ACA.Figure 7
The optimal distribution scheme of trucks-alone distribution by using ABC-ACA.Figure8 shows the optimal delivery scheme when only trucks are used for delivery by using ACA.Figure 8
The optimal distribution scheme of trucks-alone distribution by using ACA.Table3 shows the optimization results of using ABC-ACA to solve the joint delivery mode and the trucks-alone delivery.Table 3
Comparison of results.
Delivery modeAlgorithmTruckTruck routesUAVUAV routesDistribution and satisfaction cost (yuan)Joint distribution of trucks and UAVsABC-ACA10-4-7-B-C-8-D-01B-1-B1991.92B-3-11-B3C-13-B4C-15-C5D-12-D6D-2-D20-A-14-E-07A-6-10-A8E-9-E9E-5-ETrucks-only distributionABC-ACA10-4-7-1-0——2431.520-13-15-3-11-030-8-2-12-040-5-14-9-050-6-10-0Trucks-only distributionACA10-1-4-7-0——2824.720-3-15-13-11-12-8-2-030-5-9-040-14-050-6-10-0As can be seen from the above table, when using joint delivery of trucks and UAVs, only 2 trucks need to be activated. There are three joint distribution transfer stations on the path of the first truck, and a total of six UAVs are used for delivery. There are two joint distribution transfer stations on the path of the second truck, and three UAVs are used for delivery. The delivery and satisfaction cost incurred during the joint delivery of trucks and UAVs process was RMB 1991.9 yuan, the average time dissatisfaction was 8.9%, and the average goods damage dissatisfaction was 6.3%. When the trucks are used for single delivery by using ABC-ACA, it necessarily starts five trucks, all of which start from the distribution center and return to it after completing the delivery tasks. The cost of delivery and satisfaction in the process of trucks-alone delivery is RMB 2431.5 yuan, the average time dissatisfaction is 45.2%, and the average goods damage dissatisfaction is 36.4%. When the trucks are used for single delivery by using ACA, it starts five trucks, all of which start from the distribution center and return to it after completing the delivery tasks. The cost of delivery and satisfaction in the process of trucks-alone delivery is RMB 2824.7 yuan, the average time dissatisfaction is 47.8%, and the average goods damage dissatisfaction is 38.6%. From the above analysis, it is obvious that the cost of the joint delivery mode of trucks and UAVs is lower than that of the trucks-alone delivery model, and the customer satisfaction of the joint delivery model is much higher than that of the trucks-alone delivery mode. Based on the comparison results, it can also be seen that the trucks-alone delivery mode solved by the ABC-ACA has better solution results and lower cost than the nonimproved ACA. Therefore, the joint delivery mode of trucks and UAVs has advantages not only in cost but also in meeting customer needs; that is, the ABC-ACA proposed in this paper is more efficient.


## 4.1. Background Analysis and Parameter Setting

This paper takes the order of a distribution center of an e-commerce logistics enterprise in city A as the customer sample. The ABC-ACO algorithm is used to plan the joint delivery of trucks and UAVs, so as to minimize the delivery cost and maximize customer satisfaction under the above constraints. The location coordinates of 15 customer points, 1 distribution center, and 5 joint distribution transfer stations, the time window requirements of customer points, and the requirement and service time of each customer point are shown in Table1.Table 1
Information table of each node.
No.NodePosition coordinates (X,Y)Demandsqi/kgTime windowsei/hli/hEi/hLi/h0Distribution center(94,100)07207201Customer point 1(60,135)410117122Customer point 2(40,36)17811.57.512.53Customer point 3(48,96)3812712.54Customer point 4(92,154)258.513813.55Customer point 5(97,50)10101611176Customer point 6(120,90)11913.58167Customer point 7(44,160)229.514914.58Customer point 8(20,54)209.515915.59Customer point 9(108,32)5101691710Customer point 10(130,88)51116.5101711Customer point 11(56,100)511.5171117.512Customer point 12(50,68)61017.59.51813Customer point 13(43,110)181315101614Customer point 14(135,24)311719159.515Customer point 15(23,108)810199.520AJoint distribution transfer station A(124,103)0720720BJoint distribution transfer station B(52,120)0720720CJoint distribution transfer station C(30,114)0720720DJoint distribution transfer station D(50,50)0720720EJoint distribution transfer station E(105,43)0720720The distance between nodes is measured by vector distance, which can be expressed by the following equation:(37)dij=xi−xj2+yi−yj21/2The relevant parameters of trucks and UAVs are shown in Table2.Table 2
Description of relevant parameters.
Related parametersTrucks in distribution centersUAVs in joint distribution transfer stationsQuantity (vehicle, frame)510Maximum load (kg)10020Maximum transport distance (km)—30Speed (km/h)3080Transportation cost per unit distance (yuan/km)51Start-up cost (yuan/time)10020Service hours (h)0.50.5In addition, the multiple of the distance of the truck greater than the straight distanceη=0.3, time sensitivity coefficient α=0.5,β=0.8, goods damage coefficient q=0.1%, the range of goods damage rate acceptable to customers is 0,0.2%, the range of goods damage rate tolerable to customers is 0.2%,1, and the weight of objective function is ω1=0.5,ω2=0.3,ω3=0.2.


## 4.2. Result Analysis

According to the ABC-ACA described above, using MATLAB software, the joint delivery model of trucks and UAVs is solved. Through multiple simulations of the example, the parameters are set as follows:α=1, β=3, ρ=0.4, Ant_num=20, M=0.7, λ1=4, and λ2=2.Figure6 shows the route map of the optimal delivery scheme for the joint delivery model of trucks and UAVs by using ABC-ACA.Figure 6
The optimal delivery scheme for joint delivery of trucks and UAVs by using ABC-ACA.Figure7 shows the optimal delivery scheme when only trucks are used for delivery by using ABC-ACA.Figure 7
The optimal distribution scheme of trucks-alone distribution by using ABC-ACA.Figure8 shows the optimal delivery scheme when only trucks are used for delivery by using ACA.Figure 8
The optimal distribution scheme of trucks-alone distribution by using ACA.Table3 shows the optimization results of using ABC-ACA to solve the joint delivery mode and the trucks-alone delivery.Table 3
Comparison of results.
Delivery modeAlgorithmTruckTruck routesUAVUAV routesDistribution and satisfaction cost (yuan)Joint distribution of trucks and UAVsABC-ACA10-4-7-B-C-8-D-01B-1-B1991.92B-3-11-B3C-13-B4C-15-C5D-12-D6D-2-D20-A-14-E-07A-6-10-A8E-9-E9E-5-ETrucks-only distributionABC-ACA10-4-7-1-0——2431.520-13-15-3-11-030-8-2-12-040-5-14-9-050-6-10-0Trucks-only distributionACA10-1-4-7-0——2824.720-3-15-13-11-12-8-2-030-5-9-040-14-050-6-10-0As can be seen from the above table, when using joint delivery of trucks and UAVs, only 2 trucks need to be activated. There are three joint distribution transfer stations on the path of the first truck, and a total of six UAVs are used for delivery. There are two joint distribution transfer stations on the path of the second truck, and three UAVs are used for delivery. The delivery and satisfaction cost incurred during the joint delivery of trucks and UAVs process was RMB 1991.9 yuan, the average time dissatisfaction was 8.9%, and the average goods damage dissatisfaction was 6.3%. When the trucks are used for single delivery by using ABC-ACA, it necessarily starts five trucks, all of which start from the distribution center and return to it after completing the delivery tasks. The cost of delivery and satisfaction in the process of trucks-alone delivery is RMB 2431.5 yuan, the average time dissatisfaction is 45.2%, and the average goods damage dissatisfaction is 36.4%. When the trucks are used for single delivery by using ACA, it starts five trucks, all of which start from the distribution center and return to it after completing the delivery tasks. The cost of delivery and satisfaction in the process of trucks-alone delivery is RMB 2824.7 yuan, the average time dissatisfaction is 47.8%, and the average goods damage dissatisfaction is 38.6%. From the above analysis, it is obvious that the cost of the joint delivery mode of trucks and UAVs is lower than that of the trucks-alone delivery model, and the customer satisfaction of the joint delivery model is much higher than that of the trucks-alone delivery mode. Based on the comparison results, it can also be seen that the trucks-alone delivery mode solved by the ABC-ACA has better solution results and lower cost than the nonimproved ACA. Therefore, the joint delivery mode of trucks and UAVs has advantages not only in cost but also in meeting customer needs; that is, the ABC-ACA proposed in this paper is more efficient.


## 5. Conclusion

This paper proposes a joint delivery mode of trucks and UAVs for e-commerce delivery, which realizes the complementary advantages of UAVs and traditional delivery tools. A multiobjective optimization model for joint delivery is developed and the proposed model is solved by an improved ant colony algorithm. It proves that the joint delivery mode of trucks and UAVs is able to achieve lower costs, higher customer satisfaction, and better delivery results compared to the traditional truck-alone delivery mode. With e-commerce growing rapidly today, there is an urgent need for an efficient and economical delivery mode to meet market demand. As a new type of distribution tool, UAVs form a perfect complementary advantage with trucks, so that both distribution tools could give full play to their respective advantages and work together to achieve efficient and economic distribution. The joint delivery mode of trucks and UAVs provides an important tool for logistics companies to save resources, achieve economic benefits, and gain market competitiveness. The results of the research have laid a solid foundation for future research into the joint delivery of trucks and UAVs.Although the content of this paper provides a certain reference value for the future joint delivery of trucks and UAVs, the model constructed in this article is based on certain assumptions and constraints and will face more uncertainties in reality, for example, constraints on carbon emissions and the existence of regional restrictions. Considering carbon emissions and regional restrictions in a joint delivery mode of trucks and UAVs will be the focus of our future research.



---

*Source: 4670997-2021-11-17.xml*