# Discrete Optimization on Truck-Drone Collaborative Transportation System for Delivering Medical Resources

Authors: Min Lin; Yuming Chen; Rui Han; Yao Chen
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

Under the epidemic, closed management has turned a large number of communities into lonely islands, and the contactless delivery method of UAV has become the rigid demand in this special period. This paper studies a collaborative system of multi-UAV multitruck transportation, which can deliver emergency materials such as medicine to remote areas or closed communities. In this system, delivery tasks are assigned to multiple trucks and multiple drones on each truck can perform delivery tasks in parallel, thereby improving delivery efficiency. We study the routing problem of this system specifically for medical supplying road network and establish mixed-integer model and hybrid algorithm. We show by experiments that the number of trucks has more significant impact on the optimal solution than the number of drones and the performance of hybrid particle swarm optimization is better than the performance of the other algorithms.


---

## Body

## 1. Introduction

Under the epidemic, closed management has turned a large number of communities into lonely islands, and the contactless delivery method of UAV has become the rigid demand in this special period. Remote areas or closed communities usually have urgent needs for emergency supplies such as medicine. However, UAV delivery has obvious disadvantages: the load weight and load capacity of a drone are small, and the flight radius of a drone is short because the drone is powered by a battery. One solution to these shortcomings is to allow drones to work together with other types of transportation vehicles to deliver materials, which leads to a new system of collaborative transportation. For this new system, how to effectively dispatch drones and trucks, arrange the distribution path and travel time, and deliver the goods to the customer on time with minimum cost, and realize the efficient and low-cost operations of the system are new hot issues in the current academic and industry research.In a joint drone and truck delivery system, a drone can serve a customer while flying to and from a moving truck. Compared with pure drone delivery system or pure truck delivery system, this kind of collaborative delivery system has obvious advantages: the truck has a dual role of mobile warehouse and transport resources, which can increase the effective flight range of drones and allow different delivery tasks to be parallelized, and drones can extend the duration of the battery by charging or replacing batteries on trucks, and so on.Currently, the optimization of collaborative transportation system, in which trucks and unmanned aerial vehicles (UAVs) work together to complete the delivery task, has also been studied more and more. Lin et al. studied the discrete routing optimization of multi-UAV single-truck system on road network and created mixed-integer models and hybrid algorithms [1]. Agatz et al. established an integer programming to solve the travel salesman problem with UAVs [2]. Zhen et al. proposed an optimization model for different scales of routing networks and a nonlinear optimization model under different sizes of instances, respectively [3]. Luo et al. proposed a hybrid multiobjective genetic optimization for path planning of the truck-drone system [4]. AlMuhaideb et al. provided the adaptive randomized greedy search for the travel salesman problem with UAVs [5]. Gomez-Lagos et al. studied a new optimization for one-truck multidrone routing in last-mile delivery and presented a linear mixed-integer model to optimize the serving time for all clients [6]. Moshref-Javadi et al. compared some synchronized drone-truck models for cargo transportation and evaluated these models by a Drone-Truck Routing Algorithm [7]. Zhen proposed a stochastic planning formula to handle with any arbitrary distribution of deviation probability of operation time, and a robust formula suitable to the case where available probability distribution information is few [8]. Zhen et al. established a column generation to solve the original model based on set partition. In [9], Carlsson et al. concluded that the improvement of efficiency depends on the square root of the ratio of truck speed and UAV speed [10]. Zhang et al. proposed a drone-truck system as a tool of postdisaster assessment for humanitarian rescue networks, created a linear mixed-integer model, and handled this problem by column generation [11]. Das et al. proposed a new synchronization mechanism between UAV and trucks. They created a multiobjective model which contains two conflicting objectives [12]. Choi et al. formulated four cases of delivery service with and without help of UAVs and analyzed the sensitivity of driver payment rate, demand density, and so on [13]. Zhen focused on a combination of physics and probabilistic based models with truck interruption and created mixed-integer programming to optimize the expected gross travel time of driving containers [14].Although many researchers have done research on collaborative transportation, few have done research on the collaborative routing specifically for the topology structure of road network. This paper makes up for this deficiency. The main innovation point of this paper is to study the collaborative routing problem specifically for the topology structure of road network from a new perspective and propose models and new algorithms to solve the new problem. Our research is similar to the research in Lin et al. [1], but our research is aimed at multi-UAV multitruck system, while the research in Lin et al. [1] is aimed at multi-UAV single-truck system.


## 2. Problem

We introduce a collaborative system for multidrone multitruck transportation, in which delivery tasks are assigned to multiple trucks, and multiple drones on each truck can perform delivery tasks in parallel, thereby improving delivery efficiency. In the case of transportation of medical emergency supplies, a medical warehouse needs to send urgent medical supplies to a few hospitals or families who urgently need medical care. In this paper, the medical warehouse is called medical storehouse or supply center, and the hospitals or families are called medical requirement points. The medical storehouse dispatches multiple trucks to deliver medical supplies to several requirement points within the prescribed time, while, in addition, multiple drones were installed on each truck. When any truck approaches multiple requirement points at the same time, it sends multiple UAVs to transport materials for these requirement points. This is called multi-UAV parallel delivery, which enables more delivery tasks to be completed at the same time. After completing the delivery task, any UAV will fly back to the running truck to prepare for the next delivery task or charge its battery to extend its flight endurance.


### 2.1. Multidrone Multitruck System on Road Network

We useG=V,E to represent the road network, which is the network of all roads. In this symbol, E is a set of all roads, while V is a set of cross-over points of all roads, in which cross-over points are numbered as 0,1,…,n, and the 0th cross-over point is the medical storehouse in the case of medical supplying network.A road network for medical supplies is shown in Figure1. There are thirty-two cross-over points, where the 0th cross-over point is the medical storehouse. The medical storehouse 0 is requested to transport medical materials to some medical requirement points. The medical storehouse will dispatch multiple trucks to deliver these requirement points, and after having completed all the tasks, these trucks drive back to the medical storehouse.Figure 1
Sample medical supplying network, where storehouse 0 is the medical storehouse.The moving routes of multiple trucks and multiple drones are shown in Figure2, where the driving routes of Truck 1 and Truck 2 are denoted by the black thick and blue thick straight lines with arrow, respectively, and the flying routes of Drone 1 and Drone 2 are denoted by the red light and green light lines, respectively.Figure 2
The delivering process of multiple trucks and multiple drones.The delivering process of multiple drones and multiple trucks is shown in Figure2. Truck 1 loads the medical materials at the medical storehouse and follows the route indicated by the thick black line with arrow. The first route, along which it drives, is 0 ⟶ 11 ⟶ 10 ⟶ 9. Before almost arriving at the cross-over Point 9, Truck 1 dispatches Drone 1 in advance to deliver to Point a. When having delivered, Drone 1 flies back to the moving Truck 1 and loads the next medical materials and sometimes charge battery when the electric power is low. The second route, along which Truck 1 drives, is 9 ⟶ 16 ⟶ 17. After passing the cross-over Point 16, Truck 1 dispatches Drone 1 in advance to deliver to Point c. Similarly, when having delivered, Drone 1 flies back to the moving Truck 1. Before almost arriving at the cross-over Point 17, Truck 1 dispatches Drone 2 in advance to deliver to Point d, because Drone 1 is delivering to another Point c. At last, all the materials on Truck 1 were delivered and Truck 1 is allowed to drive back to the medical storehouse.Similarly, Truck 2 loads the medical materials at the medical storehouse and follows the route indicated by the thick blue line with arrow. The first route, along which it drives, is 0 ⟶ 23 ⟶ 24. Before almost arriving at the cross-over Point 23, Truck 2 dispatches Drone2 in advance to deliver to Point f. The second route, along which Truck 2 drives, is 24 ⟶ 18 ⟶ 0. After passing the cross-over Point 24, Truck 1 dispatches Drone 2 in advance to deliver to Point e. Next, Truck 2 dispatches Drone 1 in advance to deliver to Point b, because Drone 2 is delivering to another Point e. At last, all the materials on Truck 2 were delivered and Truck 2 is allowed to drive back to the medical storehouse.


### 2.2. Notational Conventions

First, we explain the following symbols:∗: we adopt Euclidean distance as in Lin et al. [1].ℜ: the two-dimensional Euclidean plane.G: road network of medical emergency supplies.n: the total of all cross-over points.V: the set of all cross-over points, V=0,1,2,3,…,n.μu: the coordinate of the uth cross-over point, which contains x-coordinate and y-coordinate:(1)μu=μu1,μu2∈ℜ,u∈V.u,v: a directed linear road, which is a directed linear segment which starts at the uth cross-over point and ends at the Vth cross-over point, where u,v∈V.εu,v: a binary number indicating whether u,v exists in the road network G. A directed linear segment from any cross-over point u to itself does not exist, that is, u,u∉E:(2)εu,v=1,ifu,v∈E,u≠v,0,ifu,v∉E,u≠v,0,ifu=v.E: the set of all directed roads, E=u,v|εu,v=1,∀u,v∈V.φ0: speed of each truck.φ1: speed of each drone, where φ0<φ1.h: the total number of medical requirement points to be served.I: the set of the medical requirement points to be delivered.i: point number of medical requirement, i∈I.Pi: the position coordinate of Requirement i, Pi=pi1,pi2.gi: the delivery volume for Requirement i.m: the total of UAVs in every truck.K: the set of all the UAVs in every truck.k: UAV number, k∈K.L: the total number of all trucks.S: the set of all trucks, S=1,2,3,…,L−1,L.s: truck number, s∈S.qs: loading capacity of Truck s.℘s: closed loop driving route of Truck s, ℘s∈ℜ.τs,k: the maximum battery endurance of the kth drone of Truck s.


### 2.3. Decision Variables

Next, we explain the following decision variables:ωs,u,v: a binary number which is one if u,v is a part of the path ℘s of Truck s; otherwise, is zero:(3)ωs,u,v=1,ifu,v∈℘s,u≠v,0,ifu,v∉℘s,u≠v,0,ifu=v.θi,s,k: a binary number which is 1 if Requirement i is served by the kth drone of Truck s; if not, it is 0.Xi: the take-off point of the drone flying from the truck to Requirement i.Yi: the landing point of the drone which flying back to the truck from Requirement i.


### 2.4. Routing Problem of the Multidrone Multitruck System

The following is the definition of the routing problem of multidrone multitruck system. In the road networkG=V,E, every requirement point is numbered as i∈I; the position coordinate and delivery volume of which are given in advance. And the 0th cross-over point is the medical storehouse.The target of the problem is to figure out the flying route of each UAV and the driving route of each truck. Each truck loads the medical materials at the medical storehouse and follows its route to deliver to its requirement points. Each drone follows its flight route to serve a requirement point while flying to and from a moving truck.


## 2.1. Multidrone Multitruck System on Road Network

We useG=V,E to represent the road network, which is the network of all roads. In this symbol, E is a set of all roads, while V is a set of cross-over points of all roads, in which cross-over points are numbered as 0,1,…,n, and the 0th cross-over point is the medical storehouse in the case of medical supplying network.A road network for medical supplies is shown in Figure1. There are thirty-two cross-over points, where the 0th cross-over point is the medical storehouse. The medical storehouse 0 is requested to transport medical materials to some medical requirement points. The medical storehouse will dispatch multiple trucks to deliver these requirement points, and after having completed all the tasks, these trucks drive back to the medical storehouse.Figure 1
Sample medical supplying network, where storehouse 0 is the medical storehouse.The moving routes of multiple trucks and multiple drones are shown in Figure2, where the driving routes of Truck 1 and Truck 2 are denoted by the black thick and blue thick straight lines with arrow, respectively, and the flying routes of Drone 1 and Drone 2 are denoted by the red light and green light lines, respectively.Figure 2
The delivering process of multiple trucks and multiple drones.The delivering process of multiple drones and multiple trucks is shown in Figure2. Truck 1 loads the medical materials at the medical storehouse and follows the route indicated by the thick black line with arrow. The first route, along which it drives, is 0 ⟶ 11 ⟶ 10 ⟶ 9. Before almost arriving at the cross-over Point 9, Truck 1 dispatches Drone 1 in advance to deliver to Point a. When having delivered, Drone 1 flies back to the moving Truck 1 and loads the next medical materials and sometimes charge battery when the electric power is low. The second route, along which Truck 1 drives, is 9 ⟶ 16 ⟶ 17. After passing the cross-over Point 16, Truck 1 dispatches Drone 1 in advance to deliver to Point c. Similarly, when having delivered, Drone 1 flies back to the moving Truck 1. Before almost arriving at the cross-over Point 17, Truck 1 dispatches Drone 2 in advance to deliver to Point d, because Drone 1 is delivering to another Point c. At last, all the materials on Truck 1 were delivered and Truck 1 is allowed to drive back to the medical storehouse.Similarly, Truck 2 loads the medical materials at the medical storehouse and follows the route indicated by the thick blue line with arrow. The first route, along which it drives, is 0 ⟶ 23 ⟶ 24. Before almost arriving at the cross-over Point 23, Truck 2 dispatches Drone2 in advance to deliver to Point f. The second route, along which Truck 2 drives, is 24 ⟶ 18 ⟶ 0. After passing the cross-over Point 24, Truck 1 dispatches Drone 2 in advance to deliver to Point e. Next, Truck 2 dispatches Drone 1 in advance to deliver to Point b, because Drone 2 is delivering to another Point e. At last, all the materials on Truck 2 were delivered and Truck 2 is allowed to drive back to the medical storehouse.


## 2.2. Notational Conventions

First, we explain the following symbols:∗: we adopt Euclidean distance as in Lin et al. [1].ℜ: the two-dimensional Euclidean plane.G: road network of medical emergency supplies.n: the total of all cross-over points.V: the set of all cross-over points, V=0,1,2,3,…,n.μu: the coordinate of the uth cross-over point, which contains x-coordinate and y-coordinate:(1)μu=μu1,μu2∈ℜ,u∈V.u,v: a directed linear road, which is a directed linear segment which starts at the uth cross-over point and ends at the Vth cross-over point, where u,v∈V.εu,v: a binary number indicating whether u,v exists in the road network G. A directed linear segment from any cross-over point u to itself does not exist, that is, u,u∉E:(2)εu,v=1,ifu,v∈E,u≠v,0,ifu,v∉E,u≠v,0,ifu=v.E: the set of all directed roads, E=u,v|εu,v=1,∀u,v∈V.φ0: speed of each truck.φ1: speed of each drone, where φ0<φ1.h: the total number of medical requirement points to be served.I: the set of the medical requirement points to be delivered.i: point number of medical requirement, i∈I.Pi: the position coordinate of Requirement i, Pi=pi1,pi2.gi: the delivery volume for Requirement i.m: the total of UAVs in every truck.K: the set of all the UAVs in every truck.k: UAV number, k∈K.L: the total number of all trucks.S: the set of all trucks, S=1,2,3,…,L−1,L.s: truck number, s∈S.qs: loading capacity of Truck s.℘s: closed loop driving route of Truck s, ℘s∈ℜ.τs,k: the maximum battery endurance of the kth drone of Truck s.


## 2.3. Decision Variables

Next, we explain the following decision variables:ωs,u,v: a binary number which is one if u,v is a part of the path ℘s of Truck s; otherwise, is zero:(3)ωs,u,v=1,ifu,v∈℘s,u≠v,0,ifu,v∉℘s,u≠v,0,ifu=v.θi,s,k: a binary number which is 1 if Requirement i is served by the kth drone of Truck s; if not, it is 0.Xi: the take-off point of the drone flying from the truck to Requirement i.Yi: the landing point of the drone which flying back to the truck from Requirement i.


## 2.4. Routing Problem of the Multidrone Multitruck System

The following is the definition of the routing problem of multidrone multitruck system. In the road networkG=V,E, every requirement point is numbered as i∈I; the position coordinate and delivery volume of which are given in advance. And the 0th cross-over point is the medical storehouse.The target of the problem is to figure out the flying route of each UAV and the driving route of each truck. Each truck loads the medical materials at the medical storehouse and follows its route to deliver to its requirement points. Each drone follows its flight route to serve a requirement point while flying to and from a moving truck.


## 3. Model

We explain the intermediate variables, and then the programming model.


### 3.1. Intermediate Variables

We use a symbolδs,u to indicate the moving mileage of Truck s from the medical storehouse to the uth cross-over point. It is easy to see: δs,0=0.If theuth cross-over point is not located on the driving route ℘s of Truck s, then a cross-over point v does not exist so that ωs,v,u=1. Let δs,u=−1 if u∉℘s.If theuth cross-over point is located on the driving route ℘s of Truck s, then only one cross-over point v exists so that ωs,v,u=1, that is, ∃v,v,u∈℘s. The line length of u,v is(4)μu−μv=μu1−μv12+μu2−μv22.We can get the following:(5)δs,u=∑v=0nωs,v,u×δs,v+μu1−μv12+μu2−μv22.In summary,(6)δs,u=0,ifu=0,∑v=0nωs,v,u×δs,v+μu1−μv12+μu2−μv22,ifu≠0,∀u∈℘s,−1,ifu≠0,∀u∉℘s.To reduce the difficulty of modelling, we use the following intermediate variables to replace variables:Xi and Yi.βi,u,v: a binary number denoting whether the launching point Xi is located on u,v:(7)βi,u,v=1,ifXi∈u,v,0,ifXi∉u,v.αi: a decimal number denoting that the distance between Xi and u is divided by the line length of u,v. Obviously, αi∈0,1:(8)αidefXi−μuμv−μu.βi,u,v∗: a binary number denoting which segment of ℘s the point Yi is located on:(9)βi,u,v∗=1,ifYi∈u,v,0,ifYi∉u,v.αi∗: a decimal number denoting that the distance between Yi and u is divided by the line length of u,v, so αi∗∈0,1:(10)αi∗defYi−μuμv−μu.According to the above intermediate variables, we can get the coordinates ofXi and Yi.xi1 is the x-coordinate of the launching point Xi:(11)xi1=∑u=0n∑v=0nβi,u,v×μu1+αi×μv1−μu1.xi2 is the y-coordinate of the launching point Xi:(12)xi2=∑u=0n∑v=0nβi,u,v×μu2+αi×μv2−μu2.yi1 is the x-coordinate of the landing point Yi:(13)yi1=∑u=0n∑v=0nβi,u,v∗×μu1+αi∗×μv1−μu1.yi2 is the y-coordinate of the landing point Yi:(14)yi2=∑u=0n∑v=0nβi,u,v∗×μu2+αi∗×μv2−μu2.We use a symbolξi,s to denote the distance of Truck s driving from the medical storehouse to launching point Xi:(15)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+xi1−μu12+xi2−μu22.This is equivalent to(16)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+αi×μv−μu.We use a symbolψi,s to denote the distance of Truck s driving from the medical storehouse to landing point Yi:(17)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+yi1−μu12+yi2−μu22.This is equivalent to(18)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+αi∗×μv−μu.We can also get the flight distance of the drone for delivering to Requirementi:(19)Xi−Pi+Pi−Yi=xi1−pi12+xi2−pi22+pi1−yi12+pi2−yi22.


### 3.2. Programming Model

(20)MinimizeR=∑i=1h∑s=1L∑k=1mθi,s,k×max1φ1Xi−Pi+Pi−Yi−1φ0ψi,s−ξi,s,0+1φ0∑s=1L∑u=0n∑v=0nωs,u,v×μu−μv.Subject to(21)ωs,u,u=0,∀s∈S∀u∈V,(22)ωs,u,v≤εu,v,∀s∈S∀u,v∈V,(23)∑u=0nωs,u,v≤∀s∈S∀v∈V,(24)∑v=0nωs,u,v≤1∀s∈S∀u∈V,(25)∑v=0nωs,u,v=∑t=0nωs,t,u,∀s∈S∀u∈V,(26)δs,0=0∀s∈S,(27)δs,u=∑v=0nωs,v,u×δs,v+μu−μv∀s∈S∀u∈Vu≠0,(28)βi,u,v≤∑s=1L∑k=1mωs,u,v×θi,s,k∀i∈I∀u,v∈V,(29)βi,u,v∗≤∑s=1L∑k=1mωs,u,v×θi,s,k∀i∈I∀u,v∈V,(30)∑u=0n∑v=0nβi,u,v=1∀i∈I,(31)∑u=0n∑v=0nβi,u,v∗=1∀i∈I,(32)xi1=∑u=0n∑v=0nβi,u,v×μu1+αi×μv1−μu1∀i∈I,(33)xi2=∑u=0n∑v=0nβi,u,v×μu2+αi×μv2−μu2∀i∈I,(34)yi1=∑u=0n∑v=0nβi,u,v∗×μu1+αi∗×μv1−μu1∀i∈I,(35)yi2=∑u=0n∑v=0nβi,u,v∗×μu2+αi∗×μv2−μu2∀i∈I,(36)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+αi×μv−μu∀i∈I∀s∈S,(37)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+αi∗×μv−μu∀i∈I∀s∈S,(38)ξi,s≤ψi,s∀i∈I∀s∈S,(39)∑s=1L∑k=1mθi,s,k=1∀i∈I,(40)∑i=1hθi,s,k×1φ1Xi−Pi+Pi−Yi≤τs,k∀s∈S∀k∈K,(41)ξi,s−ξj,s×ξi,s−ψj,s×θi,s,k×θj,s,k≥0∀i,j∈I∀s∈S∀k∈K,(42)ψi,s−ξj,s×ψi,s−ψj,s×θi,s,k×θj,s,k≥0∀i,j∈I∀s∈S∀k∈K,(43)∑i=1h∑k=1mθi,s,k×gi≤qs∀s∈S,(44)θi,s,k×gi≤ρs,k∀i∈I∀s∈S∀k∈K,The decision variables includeθi,s,k, αi, βi,u,v, αi∗, βi,u,v∗, and ωs,u,v, where βi,u,v, βi,u,v∗, θi,s,k, or ωs,u,v is a binary number which is 0 or 1, while αi∈0,1 and αi∗∈0,1.The above objective and constraints are similar to those objectives and constraints in Lin et al. [1], but our model is specifically for multiple UAVs and multiple trucks, while the model in Lin et al. [1] is specifically for multiple UAVs and single truck, so the constraints involving multiple trucks are different from the constraints in Lin et al. [1]. In the following, we only explain the constraints with large differences. For other constraints, please refer to Lin et al. [1].Constraints (9) say that if βi,u,v=1, that is, Xi∈u,v, then there exists and only exists a unique combination of s and k such that ωs,u,v×θi,s,k=1; that is, u,v∈℘s, and the i-th customer point is delivered by the k-th drone of the s-th truck. Constraints (10) say that if βi,u,v∗=1, that is, Yi∈u,v, then there exists and only exists a unique combination of s and k such that ωs,u,v×θi,s,k=1; that is, u,v∈℘s, and the i-th customer point is delivered by the k-th drone of the s-th truck.


## 3.1. Intermediate Variables

We use a symbolδs,u to indicate the moving mileage of Truck s from the medical storehouse to the uth cross-over point. It is easy to see: δs,0=0.If theuth cross-over point is not located on the driving route ℘s of Truck s, then a cross-over point v does not exist so that ωs,v,u=1. Let δs,u=−1 if u∉℘s.If theuth cross-over point is located on the driving route ℘s of Truck s, then only one cross-over point v exists so that ωs,v,u=1, that is, ∃v,v,u∈℘s. The line length of u,v is(4)μu−μv=μu1−μv12+μu2−μv22.We can get the following:(5)δs,u=∑v=0nωs,v,u×δs,v+μu1−μv12+μu2−μv22.In summary,(6)δs,u=0,ifu=0,∑v=0nωs,v,u×δs,v+μu1−μv12+μu2−μv22,ifu≠0,∀u∈℘s,−1,ifu≠0,∀u∉℘s.To reduce the difficulty of modelling, we use the following intermediate variables to replace variables:Xi and Yi.βi,u,v: a binary number denoting whether the launching point Xi is located on u,v:(7)βi,u,v=1,ifXi∈u,v,0,ifXi∉u,v.αi: a decimal number denoting that the distance between Xi and u is divided by the line length of u,v. Obviously, αi∈0,1:(8)αidefXi−μuμv−μu.βi,u,v∗: a binary number denoting which segment of ℘s the point Yi is located on:(9)βi,u,v∗=1,ifYi∈u,v,0,ifYi∉u,v.αi∗: a decimal number denoting that the distance between Yi and u is divided by the line length of u,v, so αi∗∈0,1:(10)αi∗defYi−μuμv−μu.According to the above intermediate variables, we can get the coordinates ofXi and Yi.xi1 is the x-coordinate of the launching point Xi:(11)xi1=∑u=0n∑v=0nβi,u,v×μu1+αi×μv1−μu1.xi2 is the y-coordinate of the launching point Xi:(12)xi2=∑u=0n∑v=0nβi,u,v×μu2+αi×μv2−μu2.yi1 is the x-coordinate of the landing point Yi:(13)yi1=∑u=0n∑v=0nβi,u,v∗×μu1+αi∗×μv1−μu1.yi2 is the y-coordinate of the landing point Yi:(14)yi2=∑u=0n∑v=0nβi,u,v∗×μu2+αi∗×μv2−μu2.We use a symbolξi,s to denote the distance of Truck s driving from the medical storehouse to launching point Xi:(15)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+xi1−μu12+xi2−μu22.This is equivalent to(16)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+αi×μv−μu.We use a symbolψi,s to denote the distance of Truck s driving from the medical storehouse to landing point Yi:(17)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+yi1−μu12+yi2−μu22.This is equivalent to(18)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+αi∗×μv−μu.We can also get the flight distance of the drone for delivering to Requirementi:(19)Xi−Pi+Pi−Yi=xi1−pi12+xi2−pi22+pi1−yi12+pi2−yi22.


## 3.2. Programming Model

(20)MinimizeR=∑i=1h∑s=1L∑k=1mθi,s,k×max1φ1Xi−Pi+Pi−Yi−1φ0ψi,s−ξi,s,0+1φ0∑s=1L∑u=0n∑v=0nωs,u,v×μu−μv.Subject to(21)ωs,u,u=0,∀s∈S∀u∈V,(22)ωs,u,v≤εu,v,∀s∈S∀u,v∈V,(23)∑u=0nωs,u,v≤∀s∈S∀v∈V,(24)∑v=0nωs,u,v≤1∀s∈S∀u∈V,(25)∑v=0nωs,u,v=∑t=0nωs,t,u,∀s∈S∀u∈V,(26)δs,0=0∀s∈S,(27)δs,u=∑v=0nωs,v,u×δs,v+μu−μv∀s∈S∀u∈Vu≠0,(28)βi,u,v≤∑s=1L∑k=1mωs,u,v×θi,s,k∀i∈I∀u,v∈V,(29)βi,u,v∗≤∑s=1L∑k=1mωs,u,v×θi,s,k∀i∈I∀u,v∈V,(30)∑u=0n∑v=0nβi,u,v=1∀i∈I,(31)∑u=0n∑v=0nβi,u,v∗=1∀i∈I,(32)xi1=∑u=0n∑v=0nβi,u,v×μu1+αi×μv1−μu1∀i∈I,(33)xi2=∑u=0n∑v=0nβi,u,v×μu2+αi×μv2−μu2∀i∈I,(34)yi1=∑u=0n∑v=0nβi,u,v∗×μu1+αi∗×μv1−μu1∀i∈I,(35)yi2=∑u=0n∑v=0nβi,u,v∗×μu2+αi∗×μv2−μu2∀i∈I,(36)ξi,s=∑u=0n∑v=0n∑k=1mβi,u,v×θi,s,k×δs,u+αi×μv−μu∀i∈I∀s∈S,(37)ψi,s=∑u=0n∑v=0n∑k=1mβi,u,v∗×θi,s,k×δs,u+αi∗×μv−μu∀i∈I∀s∈S,(38)ξi,s≤ψi,s∀i∈I∀s∈S,(39)∑s=1L∑k=1mθi,s,k=1∀i∈I,(40)∑i=1hθi,s,k×1φ1Xi−Pi+Pi−Yi≤τs,k∀s∈S∀k∈K,(41)ξi,s−ξj,s×ξi,s−ψj,s×θi,s,k×θj,s,k≥0∀i,j∈I∀s∈S∀k∈K,(42)ψi,s−ξj,s×ψi,s−ψj,s×θi,s,k×θj,s,k≥0∀i,j∈I∀s∈S∀k∈K,(43)∑i=1h∑k=1mθi,s,k×gi≤qs∀s∈S,(44)θi,s,k×gi≤ρs,k∀i∈I∀s∈S∀k∈K,The decision variables includeθi,s,k, αi, βi,u,v, αi∗, βi,u,v∗, and ωs,u,v, where βi,u,v, βi,u,v∗, θi,s,k, or ωs,u,v is a binary number which is 0 or 1, while αi∈0,1 and αi∗∈0,1.The above objective and constraints are similar to those objectives and constraints in Lin et al. [1], but our model is specifically for multiple UAVs and multiple trucks, while the model in Lin et al. [1] is specifically for multiple UAVs and single truck, so the constraints involving multiple trucks are different from the constraints in Lin et al. [1]. In the following, we only explain the constraints with large differences. For other constraints, please refer to Lin et al. [1].Constraints (9) say that if βi,u,v=1, that is, Xi∈u,v, then there exists and only exists a unique combination of s and k such that ωs,u,v×θi,s,k=1; that is, u,v∈℘s, and the i-th customer point is delivered by the k-th drone of the s-th truck. Constraints (10) say that if βi,u,v∗=1, that is, Yi∈u,v, then there exists and only exists a unique combination of s and k such that ωs,u,v×θi,s,k=1; that is, u,v∈℘s, and the i-th customer point is delivered by the k-th drone of the s-th truck.


## 4. Algorithm

Like the VRP or TSP problem, our problem is also NP hard, because to find the shortest or least costly truck path, in the worst case, all possible truck paths must be checked, which would be astronomical. It is considered that the large examples of this kind of problems cannot be solved by exact algorithm, and an effective approximate algorithm must be sought for this kind of problems.Considering that our problem is NP hard, we design hybrid algorithms to solve the problem in large scale. These hybrid algorithms decompose the original problem into two smaller problems: the master problem solved by particle swarm algorithm or genetic algorithm, and the child problem solved by an approximation method that we designed. To speed up problem solving, the heuristic method breaks down the child problem into four smaller problems: the delivery task allocation of the truck, the delivery order, the routing of drone delivery, and the allocation of drone delivery tasks. This makes every small problem less constrained. The nature of our solution is suboptimal because we use evolutionary algorithm.


### 4.1. Hybrid Genetic Algorithm

The hybrid genetic algorithm decomposes the whole problem into two smaller problems: a master problem solved by genetic algorithm and a child problem solved by the heuristic, as shown in Figure3.Figure 3
The flowchart of the hybrid algorithm.


#### 4.1.1. Genetic Algorithm for Solving the Master Problem

We use genetic algorithm to deal with the master problem. The genetic algorithm contains several steps: encoding and decoding of chromosomes, designing fitness function, population initialization, replication, elite selection, cross-over operation, mutation operation, producing new species, and designing termination conditions. In the following, we only explain two critical steps.(1) The Encoding and Decoding. Because the master problem only solves the optimal closed transportation path of all trucks, the chromosomes need to encode only one kind of decision variables ωs,u,v, using binary code, as shown in Figure 4. Other decision variables are handled by the child problem and need not be coded.Figure 4
The structure of the chromosome.A feasible solution corresponding to the above chromosome (i.e., transportation path scheme) can be obtained through the following decoding process. First, in the first segment of chromosome, for all genesωs,u,v with a value of 1, judge whether the corresponding directed line segment u,v can form a truck closed loop ℘s, which starts from the storehouse 0 and returns to the storehouse 0 after delivering all goods, so that a feasible solution of the master problem can be obtained.(2) The Fitness Function. For the maximization problem, the general fitness corresponds to the objective function, but, for the minimization problem, the reciprocal of the objective function is generally taken. For a solution of the master problem corresponding to an individual R, to judge its goodness, one is to see whether it meets the constraints of the problem. The second is to calculate the objective function value of its corresponding subproblem. Specifically, first, judge whether the solution of the master problem can meet the closure of the truck driving path. Then, given the solution of the master problem, the optimal flight route for UAV to deliver goods to each customer point is solved from the subproblem, and the objective function value of the subproblem is calculated. Then judge whether the solution of the subproblem can meet the order of the launching and landing point of the UAV, and whether it could meet the constraints such as the maximum endurance mileage of the UAV. In short, it depends on whether the solutions of the master problem and its corresponding subproblems meet the above constraints. If not, these solutions are determined as infeasible solutions.For an individualr, the objective function value of its child problem is Cr ; let Mr indicate whether the solution of the master problem and its corresponding child problem are feasible; Mr=0 means feasible and Mr=1 means infeasible; then the fitness Fr of the individual r can be expressed as follows:(45)Fr=∑i=1pCi+Mi×ΓCr+Mr×Γ,r=1,2,…,p−1,p,where Γ is the penalty weight (the weight takes a relatively large positive number within the value range of the objective function). The penalty weight Γ means that when the distribution path scheme is not feasible, the fitness Fr of the individual r is greatly reduced.


#### 4.1.2. Heuristic for Solving the Child Problem

The child problem is aimed to get the optimal paths of multiple drones for each requirement point based on a closed moving route of the truck obtained from the above master problem. We use the following heuristic to solve it.(1) For Every Requirement Point, Determine Which Truck to Deliver for It. For each requirement point Pi, the shortest distance from the requirement point to all the truck routes is calculated in turn. Finally, a truck s′ is selected, to the route of which the shortest distance from the demand point is the smallest of all routes of the trucks, and the customer will be delivered by the truck s′:(46)s′⇒mins∈SdPi,℘s=mins∈SminX∈℘sPi−X.(2) For Each Truck, Find Out the Order of Its Requirement Points. Next, the requirement delivery order of the truck needs to be determined for each truck, that is, which requirement the truck delivers to first and then which requirement. When the total number of requirement points is h, all possible delivery orders are factorial of h. If the exhaustive method is used to calculate all this delivery sequence, the total amount of calculation will be considerable. Therefore, we adopt the following construction algorithm to efficiently figure out a good delivering order.Based on a driving route℘s of the sth truck, for each requirement point Pi delivered by the sth truck, figure out the closest point ⊥i to Pi on this route ℘s. Then decide the requirement delivering order of the truck according to the order in which these points ⊥i appear on the route ℘s. Specifically, if ⊥i appears earlier than ⊥j on the route ℘s, Pi is delivered before Pj. Conversely, if ⊥i appears later than ⊥j, then Pi is delivered after Pj. Figure 5 shows the closest points to Pi , Pj, and Pk on the route ℘s.Figure 5
In the child problem, we decide the customer delivery order for each truck.(3) After We Get Truck Paths and Delivering Orders from the above, Figure Out Drone Paths. When finding the route ℘s of each truck and requirement delivery order, we need to handle optimization of drone routing, which can be solved by the following construction method.When we solve the above requirement delivery order, for each requirement pointPi served by a truck, we have calculated the point ⊥i closest to the requirement point Pi on the truck route. The corresponding decision variable of UAV delivery to requirement point is Xi and Yi. To save time, we must avoid that the UAV waits for the truck or the truck waits for the UAV at landing point Yi; that is, when the UAV reaches the landing point Yi, the truck also reaches the landing point Yi. Therefore, the total time of the UAV from the take-off point to the requirement point and then to the landing point should be equal to the time of the truck driving from Xi to Yi:(47)1φ0ψi−ξi≈1φ1Xi−Pi+Pi−Yi.Assuming thatXi and Yi are symmetrical about the linear segment from requirement Pi to ⊥i, that is, the distance from Xi to Pi is equal to the distance from Pi to Yi, and the distance from Xi to ⊥i is equal to the distance from ⊥i to Yi, an approximate formula can be deduced:(48)1φ0Xi−⊥i≈1φ1Xi−Pi.If it is further approximately assumed that the segment betweenXi and Yi is perpendicular to the segment between Pi and ⊥i, we can get according to the Pythagorean theorem:(49)Xi−Pi≈Xi−⊥i2+⊥i−Pi2.The approximate solution ofXi can be decided through the above two formulas. Similarly, the approximate solution of landing point coordinate Yi can be decided, as shown in Figure 6:(50)1φ0Yi−⊥i≈1φ1Yi−Pi,(51)Yi−Pi≈Yi−⊥i2+⊥i−Pi2.Figure 6
Decide the launching and landing point of the UAV in the child problem.(4) Decide θi,s,k Based on the above. After the delivery sequence of each truck and its UAV route are solved in turn through the above steps, the decision variables θi,s,k can be solved one by one through the sequential loop traversal method. The solution process is to perform the following calculations for each truck.First, for all customer demand points served by a truck, setallocated = false to indicate that the requirement point has not been assigned to a UAV of the truck.Next, for the first and second UAVs of Trucks, requirement points are allocated as follows until all requirement points are allocated to one UAV:(1)
For the first UAV of this Trucks, traverse each requirement point served by Truck s in turn according to the delivery order. First visit the first requirement point i served by Truck s, set θi,s,1=1, and set allocated = true. Then, visit the second requirement point j. If the first UAV has returned to the truck before visiting the second requirement point, set θj,s,1=1, and set allocated = true. Otherwise, set θj,s,1=0, and set allocated = false. And so on until all requirement points are traversed.(2)
For the second UAV of Trucks, also traverse each allocated = false requirement point served by Truck s in turn according to the delivery order; that is, it skips all allocated = true requirement points that have been allocated. First visit the first requirement point i marked as unassigned served by Truck s, set θi,s,2=1, and set allocated = true. Then, access the second requirement point j marked as unassigned: if the second UAV has returned to the truck when accessing this requirement point j, then set θj,s,2=1, and set allocated = true. Otherwise, set θj,s,2=0, and set allocated = false. And so on until all requirement points are traversed.Similarly, the third and fourth UAVs of Trucks are solved in the same way as the second UAV of Truck s until the values θi,s,k of all drones are solved.In short, the above calculation is performed for all trucks until the valuesθi,s,k of all UAVs for all trucks are calculated.


### 4.2. Hybrid Particle Swarm Algorithm

The hybrid particle swarm algorithm is generally similar to the hybrid genetic algorithm, as shown in Figure3.


## 4.1. Hybrid Genetic Algorithm

The hybrid genetic algorithm decomposes the whole problem into two smaller problems: a master problem solved by genetic algorithm and a child problem solved by the heuristic, as shown in Figure3.Figure 3
The flowchart of the hybrid algorithm.


### 4.1.1. Genetic Algorithm for Solving the Master Problem

We use genetic algorithm to deal with the master problem. The genetic algorithm contains several steps: encoding and decoding of chromosomes, designing fitness function, population initialization, replication, elite selection, cross-over operation, mutation operation, producing new species, and designing termination conditions. In the following, we only explain two critical steps.(1) The Encoding and Decoding. Because the master problem only solves the optimal closed transportation path of all trucks, the chromosomes need to encode only one kind of decision variables ωs,u,v, using binary code, as shown in Figure 4. Other decision variables are handled by the child problem and need not be coded.Figure 4
The structure of the chromosome.A feasible solution corresponding to the above chromosome (i.e., transportation path scheme) can be obtained through the following decoding process. First, in the first segment of chromosome, for all genesωs,u,v with a value of 1, judge whether the corresponding directed line segment u,v can form a truck closed loop ℘s, which starts from the storehouse 0 and returns to the storehouse 0 after delivering all goods, so that a feasible solution of the master problem can be obtained.(2) The Fitness Function. For the maximization problem, the general fitness corresponds to the objective function, but, for the minimization problem, the reciprocal of the objective function is generally taken. For a solution of the master problem corresponding to an individual R, to judge its goodness, one is to see whether it meets the constraints of the problem. The second is to calculate the objective function value of its corresponding subproblem. Specifically, first, judge whether the solution of the master problem can meet the closure of the truck driving path. Then, given the solution of the master problem, the optimal flight route for UAV to deliver goods to each customer point is solved from the subproblem, and the objective function value of the subproblem is calculated. Then judge whether the solution of the subproblem can meet the order of the launching and landing point of the UAV, and whether it could meet the constraints such as the maximum endurance mileage of the UAV. In short, it depends on whether the solutions of the master problem and its corresponding subproblems meet the above constraints. If not, these solutions are determined as infeasible solutions.For an individualr, the objective function value of its child problem is Cr ; let Mr indicate whether the solution of the master problem and its corresponding child problem are feasible; Mr=0 means feasible and Mr=1 means infeasible; then the fitness Fr of the individual r can be expressed as follows:(45)Fr=∑i=1pCi+Mi×ΓCr+Mr×Γ,r=1,2,…,p−1,p,where Γ is the penalty weight (the weight takes a relatively large positive number within the value range of the objective function). The penalty weight Γ means that when the distribution path scheme is not feasible, the fitness Fr of the individual r is greatly reduced.


### 4.1.2. Heuristic for Solving the Child Problem

The child problem is aimed to get the optimal paths of multiple drones for each requirement point based on a closed moving route of the truck obtained from the above master problem. We use the following heuristic to solve it.(1) For Every Requirement Point, Determine Which Truck to Deliver for It. For each requirement point Pi, the shortest distance from the requirement point to all the truck routes is calculated in turn. Finally, a truck s′ is selected, to the route of which the shortest distance from the demand point is the smallest of all routes of the trucks, and the customer will be delivered by the truck s′:(46)s′⇒mins∈SdPi,℘s=mins∈SminX∈℘sPi−X.(2) For Each Truck, Find Out the Order of Its Requirement Points. Next, the requirement delivery order of the truck needs to be determined for each truck, that is, which requirement the truck delivers to first and then which requirement. When the total number of requirement points is h, all possible delivery orders are factorial of h. If the exhaustive method is used to calculate all this delivery sequence, the total amount of calculation will be considerable. Therefore, we adopt the following construction algorithm to efficiently figure out a good delivering order.Based on a driving route℘s of the sth truck, for each requirement point Pi delivered by the sth truck, figure out the closest point ⊥i to Pi on this route ℘s. Then decide the requirement delivering order of the truck according to the order in which these points ⊥i appear on the route ℘s. Specifically, if ⊥i appears earlier than ⊥j on the route ℘s, Pi is delivered before Pj. Conversely, if ⊥i appears later than ⊥j, then Pi is delivered after Pj. Figure 5 shows the closest points to Pi , Pj, and Pk on the route ℘s.Figure 5
In the child problem, we decide the customer delivery order for each truck.(3) After We Get Truck Paths and Delivering Orders from the above, Figure Out Drone Paths. When finding the route ℘s of each truck and requirement delivery order, we need to handle optimization of drone routing, which can be solved by the following construction method.When we solve the above requirement delivery order, for each requirement pointPi served by a truck, we have calculated the point ⊥i closest to the requirement point Pi on the truck route. The corresponding decision variable of UAV delivery to requirement point is Xi and Yi. To save time, we must avoid that the UAV waits for the truck or the truck waits for the UAV at landing point Yi; that is, when the UAV reaches the landing point Yi, the truck also reaches the landing point Yi. Therefore, the total time of the UAV from the take-off point to the requirement point and then to the landing point should be equal to the time of the truck driving from Xi to Yi:(47)1φ0ψi−ξi≈1φ1Xi−Pi+Pi−Yi.Assuming thatXi and Yi are symmetrical about the linear segment from requirement Pi to ⊥i, that is, the distance from Xi to Pi is equal to the distance from Pi to Yi, and the distance from Xi to ⊥i is equal to the distance from ⊥i to Yi, an approximate formula can be deduced:(48)1φ0Xi−⊥i≈1φ1Xi−Pi.If it is further approximately assumed that the segment betweenXi and Yi is perpendicular to the segment between Pi and ⊥i, we can get according to the Pythagorean theorem:(49)Xi−Pi≈Xi−⊥i2+⊥i−Pi2.The approximate solution ofXi can be decided through the above two formulas. Similarly, the approximate solution of landing point coordinate Yi can be decided, as shown in Figure 6:(50)1φ0Yi−⊥i≈1φ1Yi−Pi,(51)Yi−Pi≈Yi−⊥i2+⊥i−Pi2.Figure 6
Decide the launching and landing point of the UAV in the child problem.(4) Decide θi,s,k Based on the above. After the delivery sequence of each truck and its UAV route are solved in turn through the above steps, the decision variables θi,s,k can be solved one by one through the sequential loop traversal method. The solution process is to perform the following calculations for each truck.First, for all customer demand points served by a truck, setallocated = false to indicate that the requirement point has not been assigned to a UAV of the truck.Next, for the first and second UAVs of Trucks, requirement points are allocated as follows until all requirement points are allocated to one UAV:(1)
For the first UAV of this Trucks, traverse each requirement point served by Truck s in turn according to the delivery order. First visit the first requirement point i served by Truck s, set θi,s,1=1, and set allocated = true. Then, visit the second requirement point j. If the first UAV has returned to the truck before visiting the second requirement point, set θj,s,1=1, and set allocated = true. Otherwise, set θj,s,1=0, and set allocated = false. And so on until all requirement points are traversed.(2)
For the second UAV of Trucks, also traverse each allocated = false requirement point served by Truck s in turn according to the delivery order; that is, it skips all allocated = true requirement points that have been allocated. First visit the first requirement point i marked as unassigned served by Truck s, set θi,s,2=1, and set allocated = true. Then, access the second requirement point j marked as unassigned: if the second UAV has returned to the truck when accessing this requirement point j, then set θj,s,2=1, and set allocated = true. Otherwise, set θj,s,2=0, and set allocated = false. And so on until all requirement points are traversed.Similarly, the third and fourth UAVs of Trucks are solved in the same way as the second UAV of Truck s until the values θi,s,k of all drones are solved.In short, the above calculation is performed for all trucks until the valuesθi,s,k of all UAVs for all trucks are calculated.


## 4.1.1. Genetic Algorithm for Solving the Master Problem

We use genetic algorithm to deal with the master problem. The genetic algorithm contains several steps: encoding and decoding of chromosomes, designing fitness function, population initialization, replication, elite selection, cross-over operation, mutation operation, producing new species, and designing termination conditions. In the following, we only explain two critical steps.(1) The Encoding and Decoding. Because the master problem only solves the optimal closed transportation path of all trucks, the chromosomes need to encode only one kind of decision variables ωs,u,v, using binary code, as shown in Figure 4. Other decision variables are handled by the child problem and need not be coded.Figure 4
The structure of the chromosome.A feasible solution corresponding to the above chromosome (i.e., transportation path scheme) can be obtained through the following decoding process. First, in the first segment of chromosome, for all genesωs,u,v with a value of 1, judge whether the corresponding directed line segment u,v can form a truck closed loop ℘s, which starts from the storehouse 0 and returns to the storehouse 0 after delivering all goods, so that a feasible solution of the master problem can be obtained.(2) The Fitness Function. For the maximization problem, the general fitness corresponds to the objective function, but, for the minimization problem, the reciprocal of the objective function is generally taken. For a solution of the master problem corresponding to an individual R, to judge its goodness, one is to see whether it meets the constraints of the problem. The second is to calculate the objective function value of its corresponding subproblem. Specifically, first, judge whether the solution of the master problem can meet the closure of the truck driving path. Then, given the solution of the master problem, the optimal flight route for UAV to deliver goods to each customer point is solved from the subproblem, and the objective function value of the subproblem is calculated. Then judge whether the solution of the subproblem can meet the order of the launching and landing point of the UAV, and whether it could meet the constraints such as the maximum endurance mileage of the UAV. In short, it depends on whether the solutions of the master problem and its corresponding subproblems meet the above constraints. If not, these solutions are determined as infeasible solutions.For an individualr, the objective function value of its child problem is Cr ; let Mr indicate whether the solution of the master problem and its corresponding child problem are feasible; Mr=0 means feasible and Mr=1 means infeasible; then the fitness Fr of the individual r can be expressed as follows:(45)Fr=∑i=1pCi+Mi×ΓCr+Mr×Γ,r=1,2,…,p−1,p,where Γ is the penalty weight (the weight takes a relatively large positive number within the value range of the objective function). The penalty weight Γ means that when the distribution path scheme is not feasible, the fitness Fr of the individual r is greatly reduced.


## 4.1.2. Heuristic for Solving the Child Problem

The child problem is aimed to get the optimal paths of multiple drones for each requirement point based on a closed moving route of the truck obtained from the above master problem. We use the following heuristic to solve it.(1) For Every Requirement Point, Determine Which Truck to Deliver for It. For each requirement point Pi, the shortest distance from the requirement point to all the truck routes is calculated in turn. Finally, a truck s′ is selected, to the route of which the shortest distance from the demand point is the smallest of all routes of the trucks, and the customer will be delivered by the truck s′:(46)s′⇒mins∈SdPi,℘s=mins∈SminX∈℘sPi−X.(2) For Each Truck, Find Out the Order of Its Requirement Points. Next, the requirement delivery order of the truck needs to be determined for each truck, that is, which requirement the truck delivers to first and then which requirement. When the total number of requirement points is h, all possible delivery orders are factorial of h. If the exhaustive method is used to calculate all this delivery sequence, the total amount of calculation will be considerable. Therefore, we adopt the following construction algorithm to efficiently figure out a good delivering order.Based on a driving route℘s of the sth truck, for each requirement point Pi delivered by the sth truck, figure out the closest point ⊥i to Pi on this route ℘s. Then decide the requirement delivering order of the truck according to the order in which these points ⊥i appear on the route ℘s. Specifically, if ⊥i appears earlier than ⊥j on the route ℘s, Pi is delivered before Pj. Conversely, if ⊥i appears later than ⊥j, then Pi is delivered after Pj. Figure 5 shows the closest points to Pi , Pj, and Pk on the route ℘s.Figure 5
In the child problem, we decide the customer delivery order for each truck.(3) After We Get Truck Paths and Delivering Orders from the above, Figure Out Drone Paths. When finding the route ℘s of each truck and requirement delivery order, we need to handle optimization of drone routing, which can be solved by the following construction method.When we solve the above requirement delivery order, for each requirement pointPi served by a truck, we have calculated the point ⊥i closest to the requirement point Pi on the truck route. The corresponding decision variable of UAV delivery to requirement point is Xi and Yi. To save time, we must avoid that the UAV waits for the truck or the truck waits for the UAV at landing point Yi; that is, when the UAV reaches the landing point Yi, the truck also reaches the landing point Yi. Therefore, the total time of the UAV from the take-off point to the requirement point and then to the landing point should be equal to the time of the truck driving from Xi to Yi:(47)1φ0ψi−ξi≈1φ1Xi−Pi+Pi−Yi.Assuming thatXi and Yi are symmetrical about the linear segment from requirement Pi to ⊥i, that is, the distance from Xi to Pi is equal to the distance from Pi to Yi, and the distance from Xi to ⊥i is equal to the distance from ⊥i to Yi, an approximate formula can be deduced:(48)1φ0Xi−⊥i≈1φ1Xi−Pi.If it is further approximately assumed that the segment betweenXi and Yi is perpendicular to the segment between Pi and ⊥i, we can get according to the Pythagorean theorem:(49)Xi−Pi≈Xi−⊥i2+⊥i−Pi2.The approximate solution ofXi can be decided through the above two formulas. Similarly, the approximate solution of landing point coordinate Yi can be decided, as shown in Figure 6:(50)1φ0Yi−⊥i≈1φ1Yi−Pi,(51)Yi−Pi≈Yi−⊥i2+⊥i−Pi2.Figure 6
Decide the launching and landing point of the UAV in the child problem.(4) Decide θi,s,k Based on the above. After the delivery sequence of each truck and its UAV route are solved in turn through the above steps, the decision variables θi,s,k can be solved one by one through the sequential loop traversal method. The solution process is to perform the following calculations for each truck.First, for all customer demand points served by a truck, setallocated = false to indicate that the requirement point has not been assigned to a UAV of the truck.Next, for the first and second UAVs of Trucks, requirement points are allocated as follows until all requirement points are allocated to one UAV:(1)
For the first UAV of this Trucks, traverse each requirement point served by Truck s in turn according to the delivery order. First visit the first requirement point i served by Truck s, set θi,s,1=1, and set allocated = true. Then, visit the second requirement point j. If the first UAV has returned to the truck before visiting the second requirement point, set θj,s,1=1, and set allocated = true. Otherwise, set θj,s,1=0, and set allocated = false. And so on until all requirement points are traversed.(2)
For the second UAV of Trucks, also traverse each allocated = false requirement point served by Truck s in turn according to the delivery order; that is, it skips all allocated = true requirement points that have been allocated. First visit the first requirement point i marked as unassigned served by Truck s, set θi,s,2=1, and set allocated = true. Then, access the second requirement point j marked as unassigned: if the second UAV has returned to the truck when accessing this requirement point j, then set θj,s,2=1, and set allocated = true. Otherwise, set θj,s,2=0, and set allocated = false. And so on until all requirement points are traversed.Similarly, the third and fourth UAVs of Trucks are solved in the same way as the second UAV of Truck s until the values θi,s,k of all drones are solved.In short, the above calculation is performed for all trucks until the valuesθi,s,k of all UAVs for all trucks are calculated.


## 4.2. Hybrid Particle Swarm Algorithm

The hybrid particle swarm algorithm is generally similar to the hybrid genetic algorithm, as shown in Figure3.


## 5. Experiment

We make experiments under Windows 10 to test the efficiency of our methods, and use C# to write these algorithms.


### 5.1. Influence of the Number of Drones and Trucks on the Optimal Solution

Through the experiment of hybrid particle swarm optimization, this section will analyse the effect of the number of drones and trucks on the completion time of collaborative delivery.Figure7 displays the influence of different numbers of UAVs and different numbers of trucks on the optimal fitness under different road network sizes and different requirement numbers, where the horizontal coordinate represents different number of trucks, (i) represents using only one truck, (ii) represents using two trucks, and (iii) represents using three trucks. The ordinate represents the best fitness. The greater the fitness, the closer to the optimal solution, and the faster the completion time of collaborative delivery. Blue bars represent using one drone, orange bars using two drones, grey bars using three drones, yellow bars using four drones, and light blue bars using five drones. Experiments (a) and (b) were conducted when the network size was 100 and the number of customers was 20 and 60, respectively. Experiments (c) were conducted when the network size was 900 and the number of customers was 60.Figure 7
The influence of different numbers of drones and trucks on the optimal solution. (a) Network size: 100, requirement number: 20. (b) Network size: 100, requirement number: 60. (c) Network size: 900, requirement number: 60.
(a)(b)(c)It can be seen that in experiment (a), when only one truck is used, the best fitness slightly exceeds 1200. When using two trucks, the optimum fitness is close to 1400. The optimum fitness was over 1600 when using 3 trucks. Similarly, in experiment (b), when only one truck was used, the best fitness did not exceed 2000. When using 2 trucks, the best fitness exceeds 2000. When using 3 trucks, the optimum fitness was 2500. Overall, the more trucks used, the better the optimum fitness.On the other hand, in experiment (a), when only one truck was used, the more drones there were, the better fitness decreased slightly. When two trucks were used, the number of drones had little effect on the optimal fitness. When three trucks were used, there was no significant difference in the best fitness for different numbers of drones. In experiment (b), when only one truck is used, when the number of UAVs increases, the best fitness increases slightly at first and then decreases slightly. When two trucks were used, the optimal fitness increased slightly first and then decreased slightly with the number of drones. A similar trend occurred when three trucks were used. In conclusion, the number of different drones has little effect on the optimal fitness.Therefore, the number of different trucks has a significant impact on the best fitness, while the number of different drones has little impact on the best fitness. In order to achieve faster collaborative delivery completion time, that is, greater optimum fitness, it is recommended to use more trucks. Using more drones did little to improve optimum fitness. When the number of UAVs increases, the optimal fitness improves slightly at the beginning, but when the number of UAVs reaches a certain number, the optimal fitness will not improve.


### 5.2. Comparison of Different Algorithms

In Figure8, we compare four algorithms under different scales of road networks and different numbers of requirement points, where the current optimal fitness is represented by the y-coordinate and the iteration number is represented by the x-coordinate. The highness of the current fitness indicates the closeness to the best solution. The changing processes of solving of pure genetic algorithm (GA), pure particle swarm (PSO), hybrid genetic algorithm (h-GA), and hybrid particle swarm (h- PSO) are denoted by the blue, grey, orange, and yellow broken lines, respectively.Figure 8
Comparison of changing process of solving of different algorithms. (a) Network size: 100, requirement number: 20. (b) Network size: 100, requirement number: 60. (c) Network size: 100, requirement number: 100. (d) Network size: 400, requirement number: 20. (e) Network size: 400, requirement number: 60. (f) Network size: 400, requirement number: 100. (g) Network size: 900, requirement number: 20. (h) Network size: 900, requirement number: 60.
(a)(b)(c)(d)(e)(f)(g)(h)We can see that the comprehensive performance of the basic algorithm is worse than that of the hybrid algorithm. And the hybrid particle swarm optimization has the best performance in all algorithms.


## 5.1. Influence of the Number of Drones and Trucks on the Optimal Solution

Through the experiment of hybrid particle swarm optimization, this section will analyse the effect of the number of drones and trucks on the completion time of collaborative delivery.Figure7 displays the influence of different numbers of UAVs and different numbers of trucks on the optimal fitness under different road network sizes and different requirement numbers, where the horizontal coordinate represents different number of trucks, (i) represents using only one truck, (ii) represents using two trucks, and (iii) represents using three trucks. The ordinate represents the best fitness. The greater the fitness, the closer to the optimal solution, and the faster the completion time of collaborative delivery. Blue bars represent using one drone, orange bars using two drones, grey bars using three drones, yellow bars using four drones, and light blue bars using five drones. Experiments (a) and (b) were conducted when the network size was 100 and the number of customers was 20 and 60, respectively. Experiments (c) were conducted when the network size was 900 and the number of customers was 60.Figure 7
The influence of different numbers of drones and trucks on the optimal solution. (a) Network size: 100, requirement number: 20. (b) Network size: 100, requirement number: 60. (c) Network size: 900, requirement number: 60.
(a)(b)(c)It can be seen that in experiment (a), when only one truck is used, the best fitness slightly exceeds 1200. When using two trucks, the optimum fitness is close to 1400. The optimum fitness was over 1600 when using 3 trucks. Similarly, in experiment (b), when only one truck was used, the best fitness did not exceed 2000. When using 2 trucks, the best fitness exceeds 2000. When using 3 trucks, the optimum fitness was 2500. Overall, the more trucks used, the better the optimum fitness.On the other hand, in experiment (a), when only one truck was used, the more drones there were, the better fitness decreased slightly. When two trucks were used, the number of drones had little effect on the optimal fitness. When three trucks were used, there was no significant difference in the best fitness for different numbers of drones. In experiment (b), when only one truck is used, when the number of UAVs increases, the best fitness increases slightly at first and then decreases slightly. When two trucks were used, the optimal fitness increased slightly first and then decreased slightly with the number of drones. A similar trend occurred when three trucks were used. In conclusion, the number of different drones has little effect on the optimal fitness.Therefore, the number of different trucks has a significant impact on the best fitness, while the number of different drones has little impact on the best fitness. In order to achieve faster collaborative delivery completion time, that is, greater optimum fitness, it is recommended to use more trucks. Using more drones did little to improve optimum fitness. When the number of UAVs increases, the optimal fitness improves slightly at the beginning, but when the number of UAVs reaches a certain number, the optimal fitness will not improve.


## 5.2. Comparison of Different Algorithms

In Figure8, we compare four algorithms under different scales of road networks and different numbers of requirement points, where the current optimal fitness is represented by the y-coordinate and the iteration number is represented by the x-coordinate. The highness of the current fitness indicates the closeness to the best solution. The changing processes of solving of pure genetic algorithm (GA), pure particle swarm (PSO), hybrid genetic algorithm (h-GA), and hybrid particle swarm (h- PSO) are denoted by the blue, grey, orange, and yellow broken lines, respectively.Figure 8
Comparison of changing process of solving of different algorithms. (a) Network size: 100, requirement number: 20. (b) Network size: 100, requirement number: 60. (c) Network size: 100, requirement number: 100. (d) Network size: 400, requirement number: 20. (e) Network size: 400, requirement number: 60. (f) Network size: 400, requirement number: 100. (g) Network size: 900, requirement number: 20. (h) Network size: 900, requirement number: 60.
(a)(b)(c)(d)(e)(f)(g)(h)We can see that the comprehensive performance of the basic algorithm is worse than that of the hybrid algorithm. And the hybrid particle swarm optimization has the best performance in all algorithms.


## 6. Conclusions

This paper focuses on a multi-UAV multitruck system, which can deliver medical materials to remote areas or closed communities. In this system, delivery tasks are assigned to multiple trucks, and multiple drones on each truck can perform delivery tasks in parallel, thereby improving delivery efficiency. We study the routing problem of this system specifically for medical supplying road network and establish mixed-integer model and hybrid algorithm. We show by experiments that the number of trucks has more significant impact on the optimal solution than the number of drones, and the performance of hybrid particle swarm optimization is better than the performance of the other algorithms.In truck-drone collaborative transportation system, optimization of route planning is a very complex problem; this paper is only a preliminary study of this problem, and the results can be further improved. In the future, research can be carried out from the following aspects: more constraints, path planning in uncertain environment, algorithm improvement, simulation optimization, and so on.



---

*Source: 1811288-2022-02-01.xml*