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

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.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 use $G=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 $\mathrm{0,1},\dots ,n$, and the 0^th cross-over point is the medical storehouse in the case of medical supplying network.

A road network for medical supplies is shown in Figure 1. There are thirty-two cross-over points, where the 0^th 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 omitted; refer to PDF]

The moving routes of multiple trucks and multiple drones are shown in Figure 2, 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 omitted; refer to PDF]

The delivering process of multiple drones and multiple trucks is shown in Figure 2. 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 Drone 2 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:

  $\ast$: we adopt Euclidean distance as in Lin et al. [1].

  $\Re$: 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=\mathrm{0,1,2,3},\dots ,n$.

  ${\mu }_u$: the coordinate of the $u^{\text{th}}$ cross-over point, which contains x-coordinate and y-coordinate:$$\begin{array}{}\text{(1)}& {\mathbf{\mu }}_u={\mu }_u^1,{\mu }_u^2\in \mathrm{\Re },\hspace{1em}u\in V.\end{array}$$

  $u,v$: a directed linear road, which is a directed linear segment which starts at the u^th cross-over point and ends at the $V^{\text{th}}$ cross-over point, where $u,v\in V$.

  ${\epsilon }_{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\notin E$:$$\begin{array}{}\text{(2)}& {\epsilon }_{u,v}=\begin{array}{cc}1,& \text{if\hspace{0.17em}}u,v\in E,\hspace{1em}u\ne v,\\ 0,& \text{if\hspace{0.17em}}u,v\notin E,\hspace{1em}u\ne v,\\ 0,& \text{if\hspace{0.17em}}u=v.\end{array}\end{array}$$

  $E$: the set of all directed roads, $E=u,v|{\epsilon }_{u,v}=1,\forall u,v\in V$.

  ${\phi }_0$: speed of each truck.

  ${\phi }_1$: speed of each drone, where ${\phi }_0<{\phi }_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\in I$.

  ${\mathbf{P}}_i$: the position coordinate of Requirement $i$, ${\mathbf{P}}_i=p_i^1,p_i^2$.

  $g_i$: 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\in K$.

  $L$: the total number of all trucks.

  $S$: the set of all trucks, $S=\mathrm{1,2,3},\dots ,L-1,L$.

  $s$: truck number, $s\in S$.

  $q_s$: loading capacity of Truck $s$.

  ${\wp }_s$: closed loop driving route of Truck $s$, ${\wp }_s\in \Re$.

  ${\tau }_{s,k}$: the maximum battery endurance of the $k^{\text{th}}$ drone of Truck $s$.

2.3. Decision Variables

Next, we explain the following decision variables:

  ${\omega }_{s,u,v}$: a binary number which is one if $u,v$ is a part of the path ${\wp }_s$ of Truck $s$; otherwise, is zero:$$\begin{array}{}\text{(3)}& {\omega }_{s,u,v}=\begin{array}{cc}1,& \text{if\hspace{0.17em}}u,v\in {\wp }_s,\hspace{1em}u\ne v,\\ 0,& \text{if\hspace{0.17em}}u,v\notin {\wp }_s,\hspace{1em}u\ne v,\\ 0,& \text{if\hspace{0.17em}}u=v.\end{array}\end{array}$$

  ${\theta }_{i,s,k}$: a binary number which is 1 if Requirement $i$ is served by the $k^{\text{th}}$ drone of Truck $s$; if not, it is 0.

  ${\mathbf{X}}_i$: the take-off point of the drone flying from the truck to Requirement $i$.

  ${\mathbf{Y}}_i$: 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 network $G=V,E$, every requirement point is numbered as $i\in I$; the position coordinate and delivery volume of which are given in advance. And the $0^{\text{th}}$ 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 ${\delta }_{s,u}$ to indicate the moving mileage of Truck $s$ from the medical storehouse to the $u^{\text{th}}$ cross-over point. It is easy to see: ${\delta }_{s,0}=0$.

If the $u^{\text{th}}$ cross-over point is not located on the driving route ${\wp }_s$ of Truck $s$, then a cross-over point $v$ does not exist so that ${\omega }_{s,v,u}=1$. Let ${\delta }_{s,u}=-1$ if $u\notin {\wp }_s$.

If the $u^{\text{th}}$ cross-over point is located on the driving route ${\wp }_s$ of Truck $s$, then only one cross-over point $v$ exists so that ${\omega }_{s,v,u}=1$, that is, $\exists v,v,u\in {\wp }_s$. The line length of $u,v$ is$$\begin{array}{}\text{(4)}& {\mathbf{\mu }}_{\mathbf{u}}-{\mathbf{\mu }}_{\mathbf{v}}=\sqrt{{{\mu }_u^1-{\mu }_v^1}^2+{{\mu }_u^2-{\mu }_v^2}^2}.\end{array}$$

We can get the following:$$\begin{array}{}\text{(5)}& {\delta }_{s,u}={\displaystyle \sum }_{v=0}^n{\omega }_{s,v,u}\times {\delta }_{s,v}+\sqrt{{{\mu }_u^1-{\mu }_v^1}^2+{{\mu }_u^2-{\mu }_v^2}^2}.\end{array}$$

In summary,$$\begin{array}{}\text{(6)}& {\delta }_{s,u}=\begin{array}{cc}0,& \text{if\hspace{0.17em}}u=0,\\ {\displaystyle \sum _{v=0}^n{\omega }_{s,v,u}\times {\delta }_{s,v}+\sqrt{{{\mu }_u^1-{\mu }_v^1}^2+{{\mu }_u^2-{\mu }_v^2}^2}},& \text{if\hspace{0.17em}}u\ne 0,\hspace{1em}\forall u\in {\wp }_s,\\ -1,& \text{if\hspace{0.17em}}u\ne 0,\hspace{1em}\forall u\notin {\wp }_s.\end{array}\end{array}$$

To reduce the difficulty of modelling, we use the following intermediate variables to replace variables: ${\mathbf{X}}_i$ and ${\mathbf{Y}}_i$.

${\beta }_{i,u,v}$: a binary number denoting whether the launching point ${\mathbf{X}}_i$ is located on $u,v$:$$\begin{array}{}\text{(7)}& {\beta }_{i,u,v}=\begin{array}{cc}1,& \text{if\hspace{0.17em}}{\mathbf{X}}_i\in u,v,\\ 0,& \text{if\hspace{0.17em}}{\mathbf{X}}_i\notin u,v.\end{array}\end{array}$$

${\alpha }_i$: a decimal number denoting that the distance between ${\mathbf{X}}_i$ and $u$ is divided by the line length of $u,v$. Obviously, ${\alpha }_i\in \mathrm{0,1}$:$$\begin{array}{}\text{(8)}& {\alpha }_i\text{def}\frac{{\mathbf{X}}_{\mathbf{i}}-{\mathbf{\mu }}_{\mathbf{u}}}{{\mathbf{\mu }}_{\mathbf{v}}-{\mathbf{\mu }}_{\mathbf{u}}}.\end{array}$$

${\beta }_{i,u,v}^{\ast }$: a binary number denoting which segment of ${\wp }_s$ the point ${\mathbf{Y}}_i$ is located on:$$\begin{array}{}\text{(9)}& {\beta }_{i,u,v}^{\ast }=\begin{array}{cc}1,& \text{if\hspace{0.17em}}{\mathbf{Y}}_i\in u,v,\\ 0,& \text{if\hspace{0.17em}}{\mathbf{Y}}_i\notin u,v.\end{array}\end{array}$$

${\alpha }_i^{\ast }$: a decimal number denoting that the distance between ${\mathbf{Y}}_i$ and $u$ is divided by the line length of $u,v$, so ${\alpha }_i^{\ast }\in \mathrm{0,1}$:$$\begin{array}{}\text{(10)}& {\alpha }_i^{\ast }\text{def}\frac{{\mathbf{Y}}_{\mathbf{i}}-{\mathbf{\mu }}_{\mathbf{u}}}{{\mathbf{\mu }}_{\mathbf{v}}-{\mathbf{\mu }}_{\mathbf{u}}}.\end{array}$$

According to the above intermediate variables, we can get the coordinates of ${\mathbf{X}}_i$ and ${\mathbf{Y}}_i$.

$x_i^1$ is the x-coordinate of the launching point ${\mathbf{X}}_i$:$$\begin{array}{}\text{(11)}& x_i^1={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}\times {\mu }_u^1+{\alpha }_i\times {\mu }_v^1-{\mu }_u^1.}}\end{array}$$

$x_i^2$ is the y-coordinate of the launching point ${\mathbf{X}}_i$:$$\begin{array}{}\text{(12)}& x_i^2={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}\times {\mu }_u^2+{\alpha }_i\times {\mu }_v^2-{\mu }_u^2}}.\end{array}$$

$y_i^1$ is the x-coordinate of the landing point ${\mathbf{Y}}_i$:$$\begin{array}{}\text{(13)}& y_i^1={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}^{\ast }\times {\mu }_u^1+{\alpha }_i^{\ast }\times {\mu }_v^1-{\mu }_u^1.}}\end{array}$$

$y_i^2$ is the y-coordinate of the landing point ${\mathbf{Y}}_i$:$$\begin{array}{}\text{(14)}& y_i^2={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}^{\ast }\times {\mu }_u^2+{\alpha }_i^{\ast }\times {\mu }_v^2-{\mu }_u^2.}}\end{array}$$

We use a symbol ${\xi }_{i,s}$ to denote the distance of Truck $s$ driving from the medical storehouse to launching point ${\mathbf{X}}_i$:$$\begin{array}{}\text{(15)}& {\xi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}\times {\theta }_{i,s,k}\times {\delta }_{s,u}+\sqrt{{x_i^1-{\mu }_u^1}^2+{x_i^2-{\mu }_u^2}^2}.}}}\end{array}$$

This is equivalent to$$\begin{array}{}\text{(16)}& {\xi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}\times {\theta }_{i,s,k}\times {\delta }_{s,u}+{\alpha }_i\times {\mu }_v-{\mu }_u}}}.\end{array}$$

We use a symbol ${\psi }_{i,s}$ to denote the distance of Truck $s$ driving from the medical storehouse to landing point ${\mathbf{Y}}_i$:$$\begin{array}{}\text{(17)}& {\psi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}^{\ast }\times {\theta }_{i,s,k}\times {\delta }_{s,u}+\sqrt{{y_i^1-{\mu }_u^1}^2+{y_i^2-{\mu }_u^2}^2}.}}}\end{array}$$

This is equivalent to$$\begin{array}{}\text{(18)}& {\psi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}^{\ast }\times {\theta }_{i,s,k}\times {\delta }_{s,u}+{\alpha }_i^{\ast }\times {\mathbf{\mu }}_{\mathbf{v}}-{\mathbf{\mu }}_{\mathbf{u}}}}}.\end{array}$$

We can also get the flight distance of the drone for delivering to Requirement $i$:$$\begin{array}{}\text{(19)}& {\mathbf{X}}_i-{\mathbf{P}}_i+{\mathbf{P}}_i-{\mathbf{Y}}_i=\sqrt{{x_i^1-p_i^1}^2+{x_i^2-p_i^2}^2}+\sqrt{{p_i^1-y_i^1}^2+{p_i^2-y_i^2}^2}.\end{array}$$

3.2. Programming Model

$$\begin{array}{c}\text{(20)}& \text{Minimize\hspace{0.17em}}R={\displaystyle \sum _{i=1}^h{\displaystyle \sum _{s=1}^L{\displaystyle \sum _{k=1}^m{\theta }_{i,s,k}\times \max \frac{1}{{\phi }_1}{\mathbf{X}}_i-{\mathbf{P}}_i+{\mathbf{P}}_i-{\mathbf{Y}}_i-\frac{1}{{\phi }_0}{\psi }_{i,s}-{\xi }_{i,s},0}}}+\\ \frac{1}{{\phi }_0}{\displaystyle \sum _{s=1}^L{\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\omega }_{s,u,v}\times {\mathbf{\mu }}_{\mathbf{u}}-{\mathbf{\mu }}_{\mathbf{v}}.}}}\end{array}$$

Subject to$$\begin{array}{}\text{(21)}& {\omega }_{s,u,u}=0,\hspace{1em}\forall s\in S\forall u\in V,\text{(22)}& {\omega }_{s,u,v}\le {\epsilon }_{u,v},\hspace{1em}\forall s\in S\forall u,v\in V,\text{(23)}& {\displaystyle \sum _{u=0}^n{\omega }_{s,u,v}}\le \hspace{1em}\forall s\in S\forall v\in V,\text{(24)}& {\displaystyle \sum _{v=0}^n{\omega }_{s,u,v}}\le 1\hspace{1em}\forall s\in S\forall u\in V,\text{(25)}& {\displaystyle \sum _{v=0}^n{\omega }_{s,u,v}}={\displaystyle \sum _{t=0}^n{\omega }_{s,t,u}},\hspace{1em}\forall s\in S\forall u\in V,\text{(26)}& {\delta }_{s,0}=0\hspace{1em}\forall s\in S,\text{(27)}& {\delta }_{s,u}={\displaystyle \sum _{v=0}^n{\omega }_{s,v,u}}\times {\delta }_{s,v}+{\mathbf{\mu }}_{\mathbf{u}}-{\mathbf{\mu }}_{\mathbf{v}}\hspace{1em}\forall s\in S\forall u\in Vu\ne 0,\text{(28)}& {\beta }_{i,u,v}\le {\displaystyle \sum _{s=1}^L{\displaystyle \sum _{k=1}^m{\omega }_{s,u,v}\times {\theta }_{i,s,k}}}\hspace{1em}\forall i\in I\forall u,v\in V,\text{(29)}& {\beta }_{i,u,v}^{\ast }\le {\displaystyle \sum _{s=1}^L{\displaystyle \sum _{k=1}^m{\omega }_{s,u,v}\times {\theta }_{i,s,k}}}\hspace{1em}\forall i\in I\forall u,v\in V,\text{(30)}& {\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}}}=1\hspace{1em}\forall i\in I,\text{(31)}& {\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}^{\ast }}}=1\hspace{1em}\forall i\in I,\text{(32)}& x_i^1={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}\times {\mu }_u^1+{\alpha }_i\times {\mu }_v^1-{\mu }_u^1}}\hspace{1em}\forall i\in I,\text{(33)}& x_i^2={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}}}\times {\mu }_u^2+{\alpha }_i\times {\mu }_v^2-{\mu }_u^2\hspace{1em}\forall i\in I,\text{(34)}& y_i^1={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}^{\ast }}}\times {\mu }_u^1+{\alpha }_i^{\ast }\times {\mu }_v^1-{\mu }_u^1\hspace{1em}\forall i\in I,\text{(35)}& y_i^2={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\beta }_{i,u,v}^{\ast }}}\times {\mu }_u^2+{\alpha }_i^{\ast }\times {\mu }_v^2-{\mu }_u^2\hspace{1em}\forall i\in I,\text{(36)}& {\xi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}\times {\theta }_{i,s,k}}}}\times {\delta }_{s,u}+{\alpha }_i\times {\mathbf{\mu }}_{\mathbf{v}}-{\mathbf{\mu }}_{\mathbf{u}}\hspace{1em}\forall i\in I\forall s\in S,\text{(37)}& {\psi }_{i,s}={\displaystyle \sum _{u=0}^n{\displaystyle \sum _{v=0}^n{\displaystyle \sum _{k=1}^m{\beta }_{i,u,v}^{\ast }\times {\theta }_{i,s,k}\times {\delta }_{s,u}+{\alpha }_i^{\ast }\times {\mathbf{\mu }}_{\mathbf{v}}-{\mathbf{\mu }}_{\mathbf{u}}}}}\hspace{1em}\forall i\in I\forall s\in S,\text{(38)}& {\xi }_{i,s}\le {\psi }_{i,s}\hspace{1em}\forall i\in I\forall s\in S,\text{(39)}& {\displaystyle \sum _{s=1}^L{\displaystyle \sum _{k=1}^m{\theta }_{i,s,k}}}=1\hspace{1em}\forall i\in I,\text{(40)}& {\displaystyle \sum _{i=1}^h{\theta }_{i,s,k}}\times \frac{1}{{\phi }_1}{\mathbf{X}}_{\mathbf{i}}-{\mathbf{P}}_{\mathbf{i}}+{\mathbf{P}}_{\mathbf{i}}-{\mathbf{Y}}_i\le {\tau }_{s,k}\hspace{1em}\forall s\in S\forall k\in K,\text{(41)}& {\xi }_{i,s}-{\xi }_{j,s}\times {\xi }_{i,s}-{\psi }_{j,s}\times {\theta }_{i,s,k}\times {\theta }_{j,s,k}\ge 0\hspace{1em}\forall i,j\in I\forall s\in S\forall k\in K,\text{(42)}& {\psi }_{i,s}-{\xi }_{j,s}\times {\psi }_{i,s}-{\psi }_{j,s}\times {\theta }_{i,s,k}\times {\theta }_{j,s,k}\ge 0\hspace{1em}\forall i,j\in I\forall s\in S\forall k\in K,\text{(43)}& {\displaystyle \sum _{i=1}^h{\displaystyle \sum _{k=1}^m{\theta }_{i,s,k}\times g_i}}\le q_s\hspace{1em}\forall s\in S,\text{(44)}& {\theta }_{i,s,k}\times g_i\le {\rho }_{s,k}\hspace{1em}\forall i\in I\forall s\in S\forall k\in K,\end{array}$$

The decision variables include ${\theta }_{i,s,k}$, ${\alpha }_i$, ${\beta }_{i,u,v}$, ${\alpha }_i^{\ast }$, ${\beta }_{i,u,v}^{\ast }$, and ${\omega }_{s,u,v}$, where ${\beta }_{i,u,v}$, ${\beta }_{i,u,v}^{\ast }$, ${\theta }_{i,s,k}$, or ${\omega }_{s,u,v}$ is a binary number which is 0 or 1, while ${\alpha }_i\in \mathrm{0,1}$ and ${\alpha }_i^{\ast }\in \mathrm{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 ${\beta }_{i,u,v}=1$, that is, ${\mathbf{X}}_i\in u,v$, then there exists and only exists a unique combination of $s$ and $k$ such that ${\omega }_{s,u,v}\times {\theta }_{i,s,k}=1$; that is, $u,v\in {\wp }_s$, and the $i$-th customer point is delivered by the $k$-th drone of the $s$-th truck. Constraints (10) say that if ${\beta }_{i,u,v}^{\ast }=1$, that is, ${\mathbf{Y}}_i\in u,v$, then there exists and only exists a unique combination of $s$ and $k$ such that ${\omega }_{s,u,v}\times {\theta }_{i,s,k}=1$; that is, $u,v\in {\wp }_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 Figure 3.

[figure omitted; refer to PDF]

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 ${\omega }_{s,u,v}$ with a value of 1, judge whether the corresponding directed line segment $u,v$ can form a truck closed loop ${\wp }_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 individual $r$, the objective function value of its child problem is $C_r$ ; let $M_r$ indicate whether the solution of the master problem and its corresponding child problem are feasible; $M_r=0$ means feasible and $M_r=1$ means infeasible; then the fitness $F_r$ of the individual $r$ can be expressed as follows:$$\begin{array}{}\text{(45)}& F_r=\frac{{\displaystyle {\sum }_{i=1}^p{C}_i+M_i\times \Gamma }}{C_r+M_r\times \Gamma },\hspace{1em}r=\mathrm{1,2},\dots ,p-1,p,\end{array}$$where $\mathrm{\Gamma }$ is the penalty weight (the weight takes a relatively large positive number within the value range of the objective function). The penalty weight $\mathrm{\Gamma }$ means that when the distribution path scheme is not feasible, the fitness $F_r$ 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 ${\mathbf{P}}_i$, the shortest distance from the requirement point to all the truck routes is calculated in turn. Finally, a truck $s^{\prime }$ 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^{\prime }$:$$\begin{array}{}\text{(46)}& s^{\prime }\Rightarrow \underset{s\in S}{\min }d{\mathbf{P}}_i,{\wp }_s=\underset{s\in S}{\min }\underset{X\in {\wp }_s}{\min }{\mathbf{P}}_i-\mathbf{X}.\end{array}$$

(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 ${\wp }_{\mathbf{s}}$ of the $s^{\text{th}}$ truck, for each requirement point ${\mathbf{P}}_i$ delivered by the $s^{\text{th}}$ truck, figure out the closest point ${\perp }_i$ to ${\mathbf{P}}_i$ on this route ${\wp }_{\mathbf{s}}$. Then decide the requirement delivering order of the truck according to the order in which these points ${\perp }_i$ appear on the route ${\wp }_{\mathbf{s}}$. Specifically, if ${\perp }_i$ appears earlier than ${\perp }_j$ on the route ${\wp }_s$, ${\mathbf{P}}_i$ is delivered before ${\mathbf{P}}_j$. Conversely, if ${\perp }_i$ appears later than ${\perp }_j$, then ${\mathbf{P}}_i$ is delivered after $P_j$. Figure 5 shows the closest points to ${\mathbf{P}}_i$ , ${\mathbf{P}}_j$, and ${\mathbf{P}}_k$ on the route ${\wp }_{\mathbf{s}}$.

[figure omitted; refer to PDF]

(3) After We Get Truck Paths and Delivering Orders from the above, Figure Out Drone Paths. When finding the route ${\wp }_{\mathbf{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 point ${\mathbf{P}}_i$ served by a truck, we have calculated the point ${\perp }_i$ closest to the requirement point ${\mathbf{P}}_i$ on the truck route. The corresponding decision variable of UAV delivery to requirement point is ${\mathbf{X}}_i$ and ${\mathbf{Y}}_i$. To save time, we must avoid that the UAV waits for the truck or the truck waits for the UAV at landing point ${\mathbf{Y}}_i$; that is, when the UAV reaches the landing point ${\mathbf{Y}}_i$, the truck also reaches the landing point ${\mathbf{Y}}_i$. 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 ${\mathbf{X}}_i$ to ${\mathbf{Y}}_i$:$$\begin{array}{}\text{(47)}& \frac{1}{{\phi }_0}{\psi }_i-{\xi }_i\approx \frac{1}{{\phi }_1}{\mathbf{X}}_i-{\mathbf{P}}_i+{\mathbf{P}}_i-{\mathbf{Y}}_i.\end{array}$$

Assuming that ${\mathbf{X}}_i$ and ${\mathbf{Y}}_i$ are symmetrical about the linear segment from requirement ${\mathbf{P}}_i$ to ${\perp }_i$, that is, the distance from ${\mathbf{X}}_i$ to ${\mathbf{P}}_i$ is equal to the distance from ${\mathbf{P}}_i$ to ${\mathbf{Y}}_i$, and the distance from ${\mathbf{X}}_i$ to ${\perp }_i$ is equal to the distance from ${\perp }_i$ to ${\mathbf{Y}}_i$, an approximate formula can be deduced:$$\begin{array}{}\text{(48)}& \frac{1}{{\phi }_0}{\mathbf{X}}_i-{\perp }_i\approx \frac{1}{{\phi }_1}{\mathbf{X}}_i-{\mathbf{P}}_i.\end{array}$$

If it is further approximately assumed that the segment between ${\mathbf{X}}_i$ and ${\mathbf{Y}}_i$ is perpendicular to the segment between ${\mathbf{P}}_i$ and ${\perp }_i$, we can get according to the Pythagorean theorem:$$\begin{array}{}\text{(49)}& {\mathbf{X}}_i-{\mathbf{P}}_i\approx \sqrt{{{\mathbf{X}}_i-{\perp }_i}^2+{{\perp }_i-{\mathbf{P}}_i}^2}.\end{array}$$

The approximate solution of ${\mathbf{X}}_i$ can be decided through the above two formulas. Similarly, the approximate solution of landing point coordinate ${\mathbf{Y}}_i$ can be decided, as shown in Figure 6:$$\begin{array}{}\text{(50)}& \frac{1}{{\phi }_0}{\mathbf{Y}}_i-{\perp }_i\approx \frac{1}{{\phi }_1}{\mathbf{Y}}_i-{\mathbf{P}}_i,\text{(51)}& {\mathbf{Y}}_i-{\mathbf{P}}_i\approx \sqrt{{{\mathbf{Y}}_i-{\perp }_i}^2+{{\perp }_i-{\mathbf{P}}_i}^2}.\end{array}$$

[figure omitted; refer to PDF]

(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 ${\theta }_{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, set allocated = 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 Truck s, requirement points are allocated as follows until all requirement points are allocated to one UAV:

(1) For the first UAV of this Truck s, 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 ${\theta }_{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 ${\theta }_{j,s,1}=1$, and set allocated = true. Otherwise, set ${\theta }_{j,s,1}=0$, and set allocated = false. And so on until all requirement points are traversed.

(2) For the second UAV of Truck s, 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 ${\theta }_{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 ${\theta }_{j,s,2}=1$, and set allocated = true. Otherwise, set ${\theta }_{j,s,2}=0$, and set allocated = false. And so on until all requirement points are traversed.

Similarly, the third and fourth UAVs of Truck s are solved in the same way as the second UAV of Truck s until the values ${\theta }_{i,s,k}$ of all drones are solved.

In short, the above calculation is performed for all trucks until the values ${\theta }_{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 Figure 3.

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.

Figure 7 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.

[figures omitted; refer to PDF]

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 Figure 8, 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.

[figures omitted; refer to PDF]

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.

Acknowledgments

This research was supported by the Key Subjects Construction Program of the Health System in Jing'an District (No. 2021PY04) and Shanghai Pujiang Program for Young Scholars (Grant No. 2020PJC061).

References

[1] M. Lin, J.-Y. Lyu, J.-J. Gao, L.-Y. Li, "Model and hybrid algorithm of collaborative distribution system with multiple drones and a truck," Scientific Programming, vol. 2020 no. 2020,DOI: 10.1155/2020/8887057, 2020.

[2] N. Agatz, P. Bouman, M. Schmidt, "Optimization approaches for the traveling salesman problem with drone," Transportation Science, vol. 52 no. 4, pp. 965-981, DOI: 10.1287/trsc.2017.0791, 2018.

[3] L. Zhen, Y. Hu, S. Wang, G. Laporte, Y. Wu, "Fleet deployment and demand fulfillment for container shipping liners," Transportation Research Part B: Methodological, vol. 120, pp. 15-32, DOI: 10.1016/j.trb.2018.11.011, 2019.

[4] Q. Luo, G. Wu, B. Ji, L. Wang, P. N. Suganthan, "Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time Windows," IEEE Transactions on Intelligent Transportation Systems,DOI: 10.1109/tits.2021.3119080, 2021.

[5] S. AlMuhaideb, T. Alhussan, S. Alamri, Y. Altwaijry, L. Aljarbou, H. Alrayes, "Optimization of truck-drone parcel delivery using metaheuristics," Applied Sciences, vol. 11 no. 14,DOI: 10.3390/app11146443, 2021.

[6] J. Gomez-Lagos, A. Candia-Vejar, F. Encina, "A new truck-drone routing problem for parcel delivery services aided by parking lots," IEEE Access, vol. 9 no. 2021, .

[7] M. Moshref-Javadi, H. Ahmad, M. Winkenbach, "A comparative analysis of synchronized truck-and-drone delivery models," Computers & Industrial Engineering, vol. 162 no. 2021, .

[8] L. Zhen, "Tactical berth allocation under uncertainty," European Journal of Operational Research, vol. 247 no. 3, pp. 928-944, DOI: 10.1016/j.ejor.2015.05.079, 2015.

[9] L. Zhen, Z. Liang, D. Zhuge, L. H. Lee, E. P. Chew, "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, vol. 106, pp. 193-217, DOI: 10.1016/j.trb.2017.10.008, 2017.

[10] J. G. Carlsson, S. Song, "Coordinated logistics with a truck and a drone," Management Science, vol. 64 no. 9, pp. 4052-4069, DOI: 10.1287/mnsc.2017.2824, 2018.

[11] G. Zhang, N. Zhu, S. Ma, J. Xia, "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, vol. 152,DOI: 10.1016/j.tre.2021.102417, 2021.

[12] D. N. Das, R. Sewani, J. Wang, M. K. Tiwari, M. K. Tiwari, "Synchronized truck and drone routing in package delivery logistics," IEEE Transactions on Intelligent Transportation Systems, vol. 22 no. 9, pp. 5772-5782, DOI: 10.1109/tits.2020.2992549, 2021.

[13] Y. Choi, P. M. Schonfeld, "A Comparison of optimized deliveries by drone and truck," Transportation Planning and Technology, vol. 44 no. 3, pp. 319-336, DOI: 10.1080/03081060.2021.1883230, 2021.

[14] L. Zhen, "Modeling of yard congestion and optimization of yard template in container ports," Transportation Research Part B: Methodological, vol. 90, pp. 83-104, DOI: 10.1016/j.trb.2016.04.011, 2016.