Comprehensive optimization of the synchronous delivery network in the model of OTMD for traveling salesman problem with drone

Abstract

Synchronous delivery with different vehicles, as an emerging concept of the delivery network, improves the efficiency of the modern logistics system significantly, which gradually gives birth to a new issue: the traveling salesman problem with drone (TSP-D). In this paper, we propose a one-truck-multiple-drone (OTMD) model on the base of the TSP-D. Compared with the traditional one-truck-one-drone (OTOD) and multiple drones models, our scheme introduces a united objective function into the optimization calculation. In terms of the proposed multiple levels iterative theory, we can compute the optimal synchronous delivery network that takes both the total delivery time and the number of drones into consideration. Four types of customer distributions are employed to investigate the OTMD model and its associated calculation approaches. Comparing the parameters of the optimal network in different delivery models, we study the relationship among the total delivery time, customer distribution and the number of serving drones. These simulation results verify the feasibility and practicality of the OTMD, and demonstrate the features of optimization calculation with different customer distributions, being beneficial to improve the efficiency of the model logistics system.

Keywords

Traveling salesman problem with drone (TSP-D)one-truck-multiple-drone (OTMD) model optimization calculation modern logistics system

1 Introduction

Drone, also known as the unmanned aerial vehicle (UAV), is an emerging technology for the last mile delivery of the products in the modern logistics system [1, 2]. Most drones developed by Amazon, Google, and DHL work at a speed of 48–64 km/h with a flight range of 16–48 km [3]. Due to their high speed and property of the flight without human operators, drones can not be restricted by worse road infrastructures. While trucks must travel on avenues and streets using rectilinear distance, drones can travel across the areas like jungles, mountains, and rivers with relative ease, and select shorter routes [4 –6]. It makes the drone access the customers faster than traditional ground transportation. Nevertheless, the disadvantages of drones are also obvious. Most drones developed by logistics companies work only have a maximum load capacity of approximate 5 lb [7]. Their batteries must be recharged and swapped after 30 min [8]. The small shipping capacity and battery run time limit the load capacity and maximum range. Therefore, many high-tech logistics companies, such as Amazon and Google, deploy some fixed depots as the base stations for supporting the operation of the drone. In addition to the technical limitations, which exist in the operating mechanism of the drones, the safety of the drones is also a significant issue in the serious flight environment, and the regulation of commercial drone deliveries [8] is still evolving. People from many developed countries are trying best to create an air traffic control criterion and system for drones, being adaptive to the development trend of the UAV [10, 11]. In the USA, the FAA and NASA have attempted to create an Unmanned Aircraft Systems (UAS) traffic management platform, for managing the safety of drones [12, 13]. Meanwhile, similar drone delivery programs are also be tested in U.K., Canada as well as the Netherlands, and have formed some preliminary systems [14].

Finally, these technical restrictions and appeals for the drone management promote the development of the working model of drones, and give birth to a new last-mile delivery concept [15] that suggests the synchronous operation of the drone and truck [16 –18]. In this delivery concept, the truck is regarded as the combination of the mobile depot and delivery vehicle, similar to the aircraft carrier in the naval field. The drones attached to the truck can depart from the truck for making a delivery, while the truck is making another delivery simultaneously. Once the drone completes a delivery, it must return to the truck at a certain delivery location. The numbers of drones and truck are variable. A truck can carry one or more drones, and a drone can also fly into one or more trucks. Some high tech companies have made attempts to realize this concept in the real world, such as the Mercedes-Benz and UPS [19, 20].

The earliest scientific problem generated from this novel concept was proposed by Murray and Chu [21] in 2015, termed as the traveling salesman problem with drone (TSP-D) or Flying Sidekick Traveling Salesman Problem (FSTSP). The essential purpose of this logistics problem is to enhance the efficiency of the synchronous delivery by optimizing the delivery route of two vehicles. However, due to the complexity of the TSP-D, the numbers of the drone and truck are both assumed to be only one. This leaves some room for improvement to involve more than one unit of the drone or truck in the model.

In this paper, we focus on creating a practical and effective working model for multiple drones in the TSP-D framework. The logistics delivery in terms of this model can be evaluated by an easy and flexible method that is more practical and reasonable than the traditional evaluation method only based on time. The main contributions of this paper are demonstrated in the following:

We propose a one-truck-multiple-drones (OTMD) model for the synchronous delivery of the drone and truck. This model of logistics delivery allows multiple drones as fast delivery vehicles, but only one truck as a collaborative vehicle.

We create a united evaluation system of the operation efficiency for the proposed OTMD model, which is the first efficiency evaluation system for different numbers of drones, to the best of our knowledge. This evaluation system not only considers the total time of the logistics delivery, but also takes the number of drones into account.

We investigate the optimal delivery network in the OTMD model from the perspective of customer node distribution, which essentially reveals the characteristics of the number of drones and the total delivery time varying with customer nodes.

The remainder of this paper is organized as follows: in Section 2, we review the literature on the TSP-D. Then, in Section 3, we describe the problem in terms of the proposed OTMD model. The detailed programming method and mathematical model of the OTMD are shown and explained in Section 4. In section 5, we investigate the features of the OTMD with some simulation comparisons. Finally, we present a conclusion in Section 6.

2 The literature review

As is an emerging concept in the modern logistics system, the coordinated delivery of the truck and drone is investigated only on the base of numerical simulation. The current investigation of this concept mainly involves two types 1) one-truck-one-drone (OTOD) model; 2) multiple-truck-multiple-drone (MTMD) model. Generally, our proposed OTMD model is a special form of the MTMD one. For the working efficiency of the coordinated delivery, a limited number of studies have emerged based upon the simplest OTOD model. But, in the complicated MTMD model, the investigations on the delivery efficiency have not been retrieved.

As the pioneer of the concept of the synchronous delivery, Murray and Chu first introduced the TSP-D. For optimizing the scheduling and routing of the coordinated delivery, they proposed the two mathematical programming models that are the flying sidekick TSP (FSTSP) and parallel drone scheduling TSP, and gave the corresponding mixed linear programming formulations as well as the heuristic solution approaches. These researches, especially the FSTSP model, construct the theoretical foundation of the TSP-D and its variants.

Agatz [22] improved the TSP-D theory of Murray and Chu [21], and pointed out that the TSP-D involves assignment decisions and routing decisions: The former determines which vehicle, truck or drone will serve which customer; and the latter determines the sequence of the customers being visited. This theory also illustrates that the improvement of the coordinated delivery efficiency of different vehicles is associated with the actual level and mathematical level.

For the OTOD model, the investigations mainly focus on optimizing the mathematical algorithm for improving the calculation efficiency of solving the TSP-D. Ha et al. [23] regarded the delivery cost as the addition of total transportation cost and waiting cost, and provided two different algorithms to minimize the time of synchronous delivery based upon the local search and Greedy Randomized Adaptive Search Procedure (GRASP). Then in terms of the delivery cost theory proposed by Ha, Yurek et al. [24] developed an iterative algorithm through decomposing the TSP-D into two stages and solving MIP models in the second stage of each iteration. Randomly generated instances with selected parameters were applied to verify this algorithm. It can solve the uniform, centered and clustered instances with a size of 12 customers effectively within a reasonable period of time.

For the MTMD model, past researches mainly aimed at improving the programming model of the TSP-D. As the first study to consider multi-trucks and multi-drones, Wang et al. [25] investigated the MTMD mode from a theoretical aspect, and introduced some worst-case results and bounds for several considerations. They investigated the MTMD mode from a theoretical aspect, and introduced some worst-case results and bounds for several considerations. Then, Ham [26] considered the TSP-D as an unrelated parallel machine scheduling problem with sequence dependent setup. Based on this theory, he proposed a constraint programming model, and tested it with the TSP-D of multiple trucks, multiple drones, multiple depots, and a hundred customers distributed across an 8-mile square area. In 2019, Kitgacharoenchai et al. [27] decomposed the TSP-D into six types according to the number of trucks and drones. They first considered the case of launching and unloading the same package in different trucks, and proposed an insertion heuristic method to solve large-sized problems for the TSP-D. Then, Wang et al. [28] designed a mixed integer programming model, and proposed a branch-and-price algorithm. In this method, a special network is used to distinguish different types of nodes and paths. To alleviate the tailing-off effect in column generation, they used column generation stabilization and calculated the alternative Lagrangian lower bound.

3 Problem description

Original research papers submitted to the IET Research Journals should conform to the IET Research Journals Length Policy [2]. The length guidelines include the abstract, references and appendices but do not include figure captions, equations, or table content. As is stated above, the models of the TSP-D are decomposed into the MTMD and OTOD models. Considered as a special version of the MTMD, the OTMD allows one truck and multiple drones to deliver packages incoordination, and must meet the following regulations and assumptions.

Each customer must be served by either the drone or the truck. Due to difficult terrains, some customers have to be visited by the drone. Conversely, due to physical restrictions or regulations, some customers have to be visited by the truck. In the standby state, the drones are on the top of the truck, which is beneficial for the launch. The routes of the truck and drones must start and end at the depot.

At the beginning of the delivery, the truck carrying all the packages and several drones depart from the depot. Each truck is assumed to have a sufficiently large capacity to carry the drones and packages through the entire operation. Drones are homogeneous with the same configuration, and have the same speed whether the package is loaded or not. The set-up and recovery times are also neglected when the drones are launched or retrieved at a particular position. Additionally, the average speed of drones must be higher than the one of the truck. In this paper, the speeds of the truck and drone are set to be 40 km/h and 60 km/h, respectively. The battery life is limited to be 20 min, and can be recharged instantaneously.

3) The depot and the customer nodes assigned to the truck are the particular positions for launching and retrieving the drones. At one operation node, the operator can launch any number of drones, but retrieve at most one drone. For one trip, a drone must be launched and retrieved at different operation nodes. Due to these regulations, the landing points of all the working drones are different, and the landing points of one drone are also different. While the drone carrying the packages departs from the truck, the truck can keep moving along its route toward the next operation node. The drone finishing the task must select one operation node to land onto the truck. If an operation node is chosen as the landing point, the truck and drone arriving at this operation node must wait for each other.

We illustrate the delivery regulations of the OTMD model in Fig. 1. This figure consists of two types of operation nodes with different shapes, which are connected by dotted and solid lines. The operation nodes in the triangle indicate the customers assigned to the drones, whereas the ones in the circle denote the customers visited by the trucks. Besides, the rectangular node expresses the depot, which is the outset and destination of the truck and drones. Meanwhile, the dotted and solid lines indicate the travel routes of the drones and truck, respectively. If the nodes 6, 7, 8 are assigned to the drones, and nodes 1, 2, 3, 4, 5 are visited by truck, we can compute and describe the serving routes of the truck and drones in the OTMD model. In Fig. 1(a), three drones participate the tasks of synchronous delivery. They fly from the truck at the depot node simultaneously, and visit the customer nodes 6,7,8 respectively. After finishing the tasks, the three drones return onto the truck at the customer nodes 2,3,4 respectively, and then travel with the truck along the remaining route. Different from the model of three drones serving three customers in Fig. 1(a), the programming routes of synchronous delivery in (b) and (c) are two serving three and one serving three, respectively. The two models also satisfy the prescribed constraints that (a) different drones can start from one operation node, but must end at different ones; (b) a drone must be launched and retrieved at different operation nodes for one trip. Note that the model of one serving one is the OTOD model as well.

Fig. 1

The synchronous delivery networks in the OTMD model with three drones (a), two drones (b) as well as one drone (c).

In our view, the proposed OTMD model involves five variables or factors that impact the final programming result for solving the TSP-D, which are the number of drones, the total delivery time, the number of customers, the positions of the customers and depot, as well as the customer demand. Undoubtedly, the customer demand is the most prioritized factor based upon the regulations or environmental conditions, and determine that the serving vehicle of the customer is the truck or drones directly. On the dependence of the effect of the customer demand, the actual TSP-D can be decomposed into three types, which are non-customer demand, complete customer demand, and partial customer demand, as shown in Fig. 2. The operation nodes having customer demand are denoted in dark color. In the case of non-customer demand, the programming result of the OTMD model completely depends on the other four variables. For the situations of partial and complete, the serving vehicles of some or all the customers are determinate, regardless of the other four variables. Another important variable is the number of drones. From Fig. 1, one can observe that different numbers of drones have different flying routes, and the number of drones has a significant effect on the mutually waiting time of two vehicles. In general, the more the drones for synchronous delivery are, the less the waiting time of the truck is, because the delivery speed of the drone is higher than the truck. But in reality, more drones can also increase the operation costs, which might exceed the saving cost of the total delivery time. Additionally, due to our proposed constraints for the OTMD, the drone number is limited to less than half of the number of operation nodes. In many cases, if the drone number arrives at a value, its increase will not save the total delivery time. Therefore, in our strategy, the objective of the problem based upon the OTMD model is to construct a united evaluation function, and compute the delivery routes of the truck and drones making the evaluation function optimal.

Fig. 2

For the same customer nodes, different customer demands result in different optimal delivery networks:(a) the serving vehicles of all the customer are uncertain; (b) node 6 is assigned to the drone, and the others are visited by the truck; (c) nodes 1,6,2 are assigned to the truck, and the serving vehicles of the other customers are uncertain. These situations are regarded as non-customer demand, complete customer demand, as well as partial customer demand.

4 Methodology

This section demonstrates a systematic programming method for the OTMD model in the TSP-D framework. As we described in the previous sections, it involves two processes that are designing a united evaluation function, and calculating the travel routes of the truck and drones in terms of the evaluation function.

4.1 United evaluation function for the OTMD model

Our papers are double column format; one column width is 8.6 cm. All paragraphs must be justified, i.e. both left-justified and right-justified.

For evaluating the delivery efficiency of the OTMD model, we consider two factors that are the total delivery time and the number of drones. The total delivery time manifests the speed of the synchronous delivery with one truck and multiple drones. In previous researches, it always is thought of as the most important or unique factor to assess the efficiency of the logistics system. However, in our OTMD model, another factor that the number of drones must be considered as well. For a special case, when the total delivery time of two programming routes is the same or very close, we will select the scheme using a smaller number of drones. The total delivery time and the number of drones both weight the final evaluation function, which can be translated into: $η = T \times {(K)}^{α}$ (1)

Here, T indicates the total delivery time, and K is the number of drones. α is the weighted parameter of the number of drones that is assumed by the operator, and greater or equal to zero. Note that when K = 1, only one drone is operated to serve the customers with the truck, and the evaluation function is only associated with the total delivery time T, which is in agreement with the actual situation perfectly. When α = 0, the total delivery time is the only consideration impacting the efficiency of synchronous delivery, regardless of the number of drones. Nevertheless, for some special cases, the available drones are less, or the capacity of the truck is too small, the number of drones is considered as the main effect on the delivery efficiency, leading to a large value of the weighted parameter. In addition to the above special situations, in general, because the delivery time is far more important than the number of drones, the weighted parameter α is always close to zero. We need to estimate a weighted parameter α based upon the mathematical theory and actual situations.

4.2 Programming method for the OTMD model

After constructing the united evaluation function, we need to program the routes of synchronous delivery with the truck and drones. The final programming routes must make the evaluation function minimum. As is presented in Equation (1), the target parameters are the number of drones K and the total delivery time T, which create a multiple levels programming problem on the whole. Therefore, the main strategy of our programming method is calculating the minimum of the total delivery time with different numbers of drones, and then taking the routes that correspond the minimum time. Detail contents of this method are organized in the following:

As we stated in section 2, customer demand is the most prioritized factor impacting the programming result. Thus, we must determine the severing vehicle (truck or drone) of certain customers based on their demand initially. The set of these special operation nodes is defined as R, in which the numbers of operation nodes served by the truck and drone are n1 and n2 respectively. The set of the total operation nodes is termed as C, involving N customers and one depot. The remaining operation nodes are in (C-R), determined by solving the TSP-D. Theoretically, the complexity of the problem and of the model mainly depends on the numbers of total operation nodes and the certain operation nodes. The larger the set C is, the less the certain operation nodes are, the higher the complexity of the TSP-D based upon OTMD is. Therefore, reasonable analysis of customer demand is an important preliminary work for programming the routes of synchronous delivery in the TSP-D framework.

After determining the operation nodes served by a certain vehicle, we can obtain the range of the number of required drones that is expressed as:

${\begin{matrix} max {1, n_{2}} \leq K \leq min {floor (\frac{N}{2}), N - n_{1}}; n_{2} < min {floor (\frac{N}{2}), N - n_{1}} \\ K = n_{2}; n_{2} \geq min {floor (\frac{N}{2}), N - n_{1}} \end{matrix}$ (2)

Here, we give the range of n_d in two situations, which are n₂ < min {floor (N/2) , N - n₁} and n₂ ≥ min {floor (N/2) , N - n₁}. For the case of n₂ < min {floor (N/2) , N - n₁}, the number of drone-served nodes through the restriction of customer demand is less than the threshold, therefore the one through the mathematical programming varies in a range. We can compute and select the optimal number of drones performing tasks from this range, making the final solution of the TSP-D satisfy the proposed OTMD model. However, When n₂ ≥ min {floor (N/2) , N - n₁}, the number of the drone-served operation nodes determined by customer demand is too large, and against the restrictions of the OTMD model that one operation node can only retrieve up to one drone. Therefore, in the paper, we only consider the situation of n₂ < min {floor (N/2) , N - n₁}. From the minimum to the maximum, we vary the number of drones in the calculated range, and calculate the optimal routes of the truck and drones with a certain K. Our programming algorithm employs the scheme of multi-level programming that consists of two stages. In the first stage, we compute the truck routes considering the truck-served nodes in set R, as shown in Fig. 3(b). In the second stage, we determine the routes of drones based upon the calculated truck route and the drone-served nodes, as shown in Fig. 3(c) and (d). To obtain the optimal truck route, all possible combinations of the truck-served nodes are calculated firstly. With the one combination, we need to find an optimal permutation or the service order of the customer that has the shortest travel route. This process can be considered as a traditional TSP, and completed fast by some heuristic methods, such as the simulated annealing algorithm, genetic algorithm, and particle swarm optimization et al. After determining the optimal route of all possible combinations of the truck-served nodes, we arrange these optimal routes from short to long, constituting a set G_k. The time of the truck traveling along these routes in set G_k are equal to the subtraction of the total delivery times and the truck waiting times. With the certain truck route that is selected serially in set G_k, all possible drone routes can be created corresponding to the certain truck time in the OTMD mode. For a certain truck route, calculating the minimum truck waiting time of all possible drone routes and adding it with the truck time, we can obtain the optimal total delivery time and corresponding synchronous delivery routes. If the optimal total delivery time in terms of a certain truck route is less than the truck time based upon the next truck route in set T, the iterative process will terminate. The synchronous delivery routes corresponding to this certain truck route is the optimal result for a certain number of drones K. Bring the optimal total delivery time and K into the united evaluation function Equation (1), the delivery efficiency η is calculated in the OTMD model. Following the above method, we can obtain the values of delivery efficiency η for all possible numbers of drones, the minimum value of which is the optimal solution. The synchronous delivery scheme corresponding to this solution is the final optimal result.

Fig. 3

The schematic diagrams of multiple level programming: (a) serving vehicles of all customer nodes are uncertain; (b) according to the customer demand, serving vehicles of some customer nodes are determined, (c) with the certain severing vehicles, optimal truck routes are determined, (d) based upon the optimal truck routes, optimal number, and routes of drones are determined.

For a better understanding, we illustrated this programming algorithm in Table 1. Assume that a logistics network consists of four customers and one depot that are termed as nodes 1, 2, 3, 4, 0 respectively, as demonstrated in Fig. 4. Among them, the package of node 1 is very heavy, and exceeds 15 lb, thereby having to be served by the truck. By Equation (2), we calculate the range of the number of drones K from 1 to 2. When K = 1, the maximum number of customer nodes assigned to the drones is floor (5/2)=2. We generate all possible combinations of truck-served nodes, and arrange them according to the optimal travel time from short to long, as shown in Table 2. For the route of 0-1-2-0, the truck travels along this route and visits the customer node1 and 2, while a drone on this truck performs two takeoffs and landings for serving the customer node 3 and 4 in the OTMD model. We simulate this process, and calculate the time of the truck waiting for the drone as 25.7 min, which plus the truck travel time 46.5 min equals the total delivery time 72.2 min. Because this time is larger than the next travel time 48.3 min, the calculation continues. Until the third route 0-1-2-4-0, as shown in Fig. 4(a), the total delivery time 60.6 min is less than the next travel time 74 min, therefore the iterative calculation terminates, and 60.6 min is regarded as the optimal delivery time when K = 1.

Table 1

The programming process in the OTMD model

Optimal route	Truck travel time/min	Waiting time/min	Total time/min	Optimal time/min	K	η (α = 0 .02)
0-1-2-0	46.5	25.7	72.2	72.2	1	72.2
0-1-4-0	48.3	23.8	72.1	72.1	1	72.1
0-1-2-4-0	60.6	0	60.6	60.6	1	60.6
0-1-3-0	74.0
0-1-3-4-0	76.6
0-1-2-3-0	78.1
(0-1-2-3-4-0)	80.6
0-1-2-0	46.5	9.6	56.1	56.1	2	56.8
0-1-4-0	48.3	7.7	56.0	56.0	2	56.8
0-1-3-0	74.0

Fig. 4

The optimal synchronous delivery network with K = 1(a) and K = 2(b).

Table 2

Indexes, sets, parameters as well as decision variables

Indexes
i,j,m	Customer node
p	Drone tour
g	All possible combinations of the truck-served nodes
k	Drone ordinal in the set F_K
K	Numbers of drones in set F_K
Sets
C	Set of all customer nodes and one depot
R	Set of some special customer nodes severed by a certain vehicle (truck or drone)
F _K	Set of K drones.
G _K	Set of all possible combinations of the truck-served nodes with K drones
P _K	Set of drone tours with the K drones
D _K	Set of customer nodes served by the drone in the case of K drones
Parameters
d _pk	During tour p of the drone k
a _ipk	1 if the customer node i is served by the drone k in tour p and 0 otherwise
f _ipk	1 if tour p of the drone k starts from node i and 0 otherwise 0
l _ipk	1 if tour p of the drone k ends at node i and 0 otherwise 0
N	Number of customer nodes in the delivery system
r	Number of customer nodes in Set R
n₁, n₂	Number of trucks and drones in Set R
{0}	Depot node
α	Weighted parameter
x _pk	1 if tour p is traveled by the drone k and 0 otherwise
Decision variables
η	United evaluation function
T _Kg	Optimal Total delivery time with K drones and combination g in the set G_K
T _opt	Optimal total delivery time
W _Kg	Truck travel time with K drones and combination g in the set G_K
w _ig	Waiting time of the truck at the operation node i with the combination g in set G_K

For the case of K = 2, the number of customer nodes assigned to the drone must be two, so the optimal truck routes are 0-1-2-0, 0-1-3-0, and 0-1-4-0. With the OTMD model, the waiting time of the truck and the total delivery time can be calculated. Due to more drones used in the synchronous delivery, the waiting time of the truck shrinks drastically, compared with the case of K = 1. For the truck route 0-1-4-0, the waiting time of the truck reduces to 7.7 min, resulting in that the final optimal time is only 56 min. If the weighted parameter α is assumed to be 0.2, the value of the evaluation function equals 56.8 that is less than the one of 60.6 in the case of K = 1. Therefore, the optimal routes of synchronous delivery are the truck route of 0-1-4-0 and two drone routes of 0-2-1,0-3-4, as demonstrated in Fig. 4(b). At the depot 0, two drones fly apart from the truck, then land on the truck at nodes 1 and 4 respectively after completing the tasks.

4.3 Mathematical model

In this section, we demonstrate the mathematical model that optimally determines the total routes of the synchronous delivery in the OTMD model. The definitions of the indexes, parameters, sets as well as variables are listed in Table 2. We decompose all the variables into certain variables (set R) and the unknown variables (set (C-R)), which are determined by the customer demand and solving the TSP-D, respectively.

In our strategy, the routes programming of synchronous delivery contains three stages. The determination of the certain variables is the first, which performs according to the environmental condition, package weight, government rules and regulations that are all regarded as customer demands. By this process, some operation nodes can be assigned to a certain severing vehicle (truck or drone), which simplifies the calculation process of route programming with ease. Then, we can calculate all possible the truck-served nodes by the combination of (C - R): $G_{K} \in Combination (C - R)$ (3)

The second stage for solving the TSP-D is to determine the number of drones, which must refer to the results of the first stage. With a certain number of drones, in the third stage, we compute the delivery routes of the truck and drones by the method of multiple iterations that is a dual-level programming process. Initially, the optimal travel route of the truck is determined by solving the TSP with some heuristic algorithms. Then, in terms of the optimal truck route, we calculate the optimal routes of drones by the use of truck waiting time w_ig that is restricted by: $\begin{matrix} max {0, \sum_{p \in P} {d_{pk} l_{ipk} x_{pk} - \\ (t_{ik} l_{ipk} x_{pk} - \sum_{j \in C ∖ D \cup {0}} t_{jk} f_{jpk} x_{pk})}} \leq w_{ig}, \\ i \in C ∖ D_{K} \cup {0}, g \in G_{K} \end{matrix}$ (4)

It illustrates that the faster the drone arrives at the operation node, the less the truck waiting time is.If the drone reaches the node earlier than the truck, the truck waiting time will be 0.

With the truck waiting time, we can calculate the total time of synchronous delivery directly: $T_{Kg} = min {\sum_{i \in C / D \cup {0}} w_{ig} | g \in G_{K}} + W_{Kg}$ (5)

According to Equation (5), the total time is equal to the sum of truck travel time W_Kg and truck waiting times w_ig at different operation nodes.

If a customer node is served by the drone, one tour must be assigned exactly, thereby only one drone serving this customer, which can be expressed as Equation (6). $\sum_{p \in P_{K}} a_{ipk} x_{pk} = 1, i \in D_{K}$ (6)

Additionally, the drone routes must satisfy the basic restrictions of the OTMD: ${\begin{matrix} \sum_{p \in P_{K}} \sum_{k = 1}^{K} f_{ipk} x_{pk} \leq K, \\ \sum_{p \in P_{K}} \sum_{k = 1}^{K} l_{ipk} x_{pk} \leq 1, \end{matrix} i, j \in C ∖ D_{K} \cup {0}; j \neq i$ (7)

$\begin{matrix} \sum_{p \in P_{K}} f_{mpk} x_{pk} + \sum_{p \in P_{K}} l_{mpk} x_{pk} \leq 2 \\ (1 - \sum_{p \in P_{K}} f_{ipk} l_{jpk} x_{pk}), \\ i, j \in C ∖ D_{K} \cup {0}, m \in {h | i < h < j}, j \neq i \end{matrix}$ (8)

According to Equation (7), at one operation node, we can launch multiple drones, but retrieve one drone at most; for one trip of a drone, the operation nodes of launching and retrieving must be different. The last feasibility condition is presented by Equation (8), which illustrates that if a tour from node i to node j is selected for one drone, these drones can not launch or retrieve at any operation nodes between i and j. These regulations ensure the feasibility and regularity of synchronous delivery with one truck and multiple drones. Finally, based upon the united evaluation function, we obtain the optimal solution of the TSP-D in the OTMD model, which can be translated into the following mathematical formulas: $\begin{matrix} {T_{opt}, K_{opt}} = {T_{Kg}, K | min {η | g \in G_{K}}} \\ = {T_{Kg}, K | min {T_{Kg} K^{α} | g \in G_{K}}} \end{matrix}$ (9)

The optimal delivery routes of truck and drones have relation to the total delivery time and the number of drones, which depends on the proposed united evaluation function.

5 Results and discussion

As a novel logistics model of synchronous delivery, the OTMD is regarded as a hybrid of the OTOD and MTMD. Compared with the traditional OTOD model described by Murray and Chu, it is more complicated, and allows more drones to be applied for enhancing the efficiency of the delivery network. Meanwhile, it also can be used as a basic model unit to constitute more complex logistics models. For shedding light on the characteristics of the proposed OTMD model as well as our programming method, we simulate four types of operation node distributions, and compare the optimal results of the four delivery models. Random distribution is the first simulated distribution, in which the customer nodes are distributed between 0 to 10 km randomly, and constitute a delivery network of 100km². Similarly, the customer nodes are distributed between 0 to 10 km uniformly, which is the second uniform distribution. Inspired by Agatz et al, we propose the second and third types of instances that are single-centered and multiple-centered distribution respectively. In the single-centered distribution, the operation nodes are located at a distance r from the center (0,0) with an angle α. The distance r follows the normal distribution N(0,l), and the angle α satisfies the uniform distribution U (02π). As an extension, we set two centers that operation nodes surround as (0,0) and (10,0), termed as multiple-centered distribution, for increasing the complexity of the delivery network. In the four-node distributions, some operation nodes are selected as certain nodes for simulating customer demand. The number of certain nodes is assumed to blow one-third of total customer nodes, thereby making the simulation more authentic. Finally, the location of the depot is also set to be (0,0).

In terms of the OTMD and OTOD models, we calculate the optimal total times and related solutions of ten sets of randomly distributed data with N = 6. For the reason that multiple drones are employed for the synchronous delivery, nearly all the solutions by the OTMD model are better than the ones by the OTOD, shown as in Table 3. More drones can save more waiting time of the truck, and make the truck travel time up to the theoretical limit. For data 2, 4, 8, three drones are used to deliver the packages, which can reduce 30.2%, 17.3%, and 23.6% optimal times in the OTOD model, respectively. However, the more drones are used in the delivery network, the more complicated the launching and retrieving operations are, and the higher the operating cost of the logistics system is. Therefore, we need the united evaluation function to weight the shortest delivery time and the number of severing drones. Employing the least drones complete the synchronous delivery fastest is our objective. In Table 3, it can be found that the realization of optimal synchronous delivery network usually can not need the most drones. For instance, only two drones can we obtain the least delivery time for data 2,6,9,10. Moreover, for some special distributions of customer nodes, such as data 5, the programming results by OTMD and OTOD delivery models are the same, which means that only one drone is enough to realize the optimal synchronous delivery. In these cases, one drone serving multiple customer nodes wastes less truck waiting time, as shown in Fig. 1(c). At last, we compute the averages of related solutions, and conclude that 2.3 drones can result in a 14.7% reduction of the total delivery time, compared with one drone.

Table 3
Simulation results in the models of OTMD and OTOD

OTMD OTOD

Customer nodes r Truck travel Waiting Optimal K η (α = 0 . 02) Drone Served Truck travel Waiting Optimal η (α = 0.02)

time/min time/min Total time/min nodes time/min time/min total time/min

1 (5,3.6), (3.7,8.5), (9.8,8.8), (8.4,2.5), (0.9,5.9), (6.6,6.6) 1 31.5 0 31.5 2 31.9 3 31.5 3.1 34.6 34.6

2 (1.1,9), (8,8.4), (7,4.2), (2.1,2.9), (1.2,8.5), (7.2,3.1) 2 26.4 0 26.4 3 27.0 2 37.4 0.4 37.8 37.8

3 (0.6,9), (6.6,5.8), (6.9,0.7) (3.2,8.2), (8.4,3.9), (8.5,6) 1 32.8 0 32.8 2 33.3 3 32.8 4.0 36.8 36.8

4 (8.2,6.2), (7.3,8.2), (7.5,4.5), (5.1,8.8), (0.6,5.9), (2.4,0.6) 1 31.5 0 31.5 3 32.2 1 38.1 0 38.1 38.1

5 (7.2,8.8), (4.4,8.7), (9.8,5.3), (9.3,9.9), (0.6,8), (7.5,9.5) 2 37.6 0 37.6 1 37.6 3 37.6 0 37.6 37.6

6 (3.5,6.7), (5.6,3.6), (0.2,2), (9.6,9), (4.1,7.4), (0.6,7.9) 1 25.7 0 25.7 2 26.1 2 29.1 0 29.1 29.1

7 (0.9,7.6), (5.5,1.7), (5.8,2.9), (3.5,9.8), (8.3,6.8), (5.6,8) 1 32.2 1.7 33.9 2 34.4 1 36.5 6.5 43 43

8 (9.3,2.6), (7.2,8.3), (7.7,3), (8.9,1.7), (6.6,5.4), (9.4,7.8) 1 29.9 2.5 32.4 3 33.1 1 42.4 0 42.4 42.4

9 (5.6,1.7), (3.2,1.1), (2.5,9.9), (2.3,8.8), (3.5,8.1), (1.4,8.4) 1 29.2 0 29.2 2 29.6 2 31.5 0 31.5 31.5

10 (7.6,0.2), (8.9,1.5), (9.2,7.4), (8.8,8.9), (10,1.1), (0.9,8.8) 1 30.5 5.1 35.6 3 36.4 2 43.2 0 43.2 43.2

Average 30.73 0.93 31.66 2.3 32.16 2 36.01 1.4 37.4 37.4

		OTMD	OTOD
	Customer nodes	r	Truck travel	Waiting	Optimal	K	η (α = 0 . 02)	Drone Served	Truck travel	Waiting	Optimal	η (α = 0.02)
			time/min	time/min	Total time/min			nodes	time/min	time/min	total time/min
1	(5,3.6), (3.7,8.5), (9.8,8.8), (8.4,2.5), (0.9,5.9), (6.6,6.6)	1	31.5	0	31.5	2	31.9	3	31.5	3.1	34.6	34.6
2	(1.1,9), (8,8.4), (7,4.2), (2.1,2.9), (1.2,8.5), (7.2,3.1)	2	26.4	0	26.4	3	27.0	2	37.4	0.4	37.8	37.8
3	(0.6,9), (6.6,5.8), (6.9,0.7) (3.2,8.2), (8.4,3.9), (8.5,6)	1	32.8	0	32.8	2	33.3	3	32.8	4.0	36.8	36.8
4	(8.2,6.2), (7.3,8.2), (7.5,4.5), (5.1,8.8), (0.6,5.9), (2.4,0.6)	1	31.5	0	31.5	3	32.2	1	38.1	0	38.1	38.1
5	(7.2,8.8), (4.4,8.7), (9.8,5.3), (9.3,9.9), (0.6,8), (7.5,9.5)	2	37.6	0	37.6	1	37.6	3	37.6	0	37.6	37.6
6	(3.5,6.7), (5.6,3.6), (0.2,2), (9.6,9), (4.1,7.4), (0.6,7.9)	1	25.7	0	25.7	2	26.1	2	29.1	0	29.1	29.1
7	(0.9,7.6), (5.5,1.7), (5.8,2.9), (3.5,9.8), (8.3,6.8), (5.6,8)	1	32.2	1.7	33.9	2	34.4	1	36.5	6.5	43	43
8	(9.3,2.6), (7.2,8.3), (7.7,3), (8.9,1.7), (6.6,5.4), (9.4,7.8)	1	29.9	2.5	32.4	3	33.1	1	42.4	0	42.4	42.4
9	(5.6,1.7), (3.2,1.1), (2.5,9.9), (2.3,8.8), (3.5,8.1), (1.4,8.4)	1	29.2	0	29.2	2	29.6	2	31.5	0	31.5	31.5
10	(7.6,0.2), (8.9,1.5), (9.2,7.4), (8.8,8.9), (10,1.1), (0.9,8.8)	1	30.5	5.1	35.6	3	36.4	2	43.2	0	43.2	43.2
	Average		30.73	0.93	31.66	2.3	32.16	2	36.01	1.4	37.4	37.4

To investigate the optimal delivery time as the numbers of customers and drones in different models of synchronous delivery, we simulate 150 sets of customer nodes with the number of drones from 6 to 20. Every number involves 10 sets that are used to calculate an average of the optimal delivery time as described in Table 3. As is shown in Fig. 5, the OTMD, OTOD as well as the basic model of one truck (OT) are applied to compute the optimal delivery network. As an important parameter in the delivery network, the number of serving customers impacts the total delivery time significantly. With more drones allowed in the OTMD model than in the other models, we can spend less time completing the delivery tasks in all ranges of the number of customers, as demonstrated in Fig. 5(a). Due to no drones applied, the delivery in the OT model is the slowest. For the curve trend, because the complexity of the delivery network increases as the number of customers, all the total delivery time of tree models rise. However, the total delivery time in the OT model increases faster, being approximately twice more than in the other models. It illustrates that using the faster drone in the delivery can improve the efficiency of the logistics system effectively, especially for a large number of customer nodes. In addition, comparing the curves of the OTMD and OTOD delivery models, one can found that the difference between them is nearly a stable value. This phenomenon is mainly because the OTMD and OTOD have similar restrictions for the optimal number of customer nodes served by the truck. According to the programming method of synchronous delivery, the total delivery time equals to the truck travel time adding the truck waiting time. With reasonable delivery planing of two vehicles, in most cases, the truck waiting time approaches zero, which means that the total delivery mainly depends on the truck travel time. For the OTMD model, more drones are used in the delivery network, resulting in that the customer nodes visited by the truck are less than the ones for the OTOD model. In our simulations, the difference between them is around 1, so the truck travel times derived in the OTMD and OTOD models have a relatively stable difference, and the curves of total delivery times via the number of customers in the two delivery models are similar.

Fig. 5

The optimal total delivery time (a) and the number of customers (b) vary with the number of customers in OTMD, OTOD and OT models.

To further explore the optimal mechanism of the delivery network in the OTMD model, we plot the optimal number of drones via the number of customer nodes. As is shown in Fig. 5(b), the curve fluctuates around a fixed value from 2 to 3 slowly in all the ranger, which illustrates that only two or three drones in the delivery network, can we spend the minimum time to complete an effective synchronous delivery. These results maybe relate to the number and distribution of the customer nodes, but still manifests that in the synchronous delivery of large customer numbers, few serving drones (two or three drones) can realize the fastest delivery. Moreover, the structure of these optimal delivery networks is very regular, and can be described as a multi-grid form, as shown in Fig. 6. Following this structure form, the entire synchronous delivery network is decomposed into some launching and retrieval units, as depicted in Fig. 6(d). In our view, the ratio between the drones and truck routes in this unit is the most important factor determining the truck waiting time. The smaller this ratio is, the shorter the truck waiting time is in one operating unit.

Fig. 6

The schematic diagrams of the optimal synchronous delivery network with one (a), two (b) and three (c) drones in the OTMD model. Three units of one, two and three drones are compared with each other (d)

For one drone, in a unit, the truck travels between two neighboring customer nodes, and the launching and retrieval of the aircraft have the shortest interval, as shown in Fig. 6(a). This structure results in the largest ratio between the drone and truck routes, as characterized in Fig. 6(d), and makes the truck waiting for the flying drone for the longest time. However, for the case of two or three drones, in a launching and retrieval unit, the delivery routes of the truck and drone are longer than for single drones, thereby decreasing the proportion between the drone and truck routes and saving the truck waiting time.

To investigate the effect of different customer distributions on the programming results, we employ uniform, single-centered and multiple-centered customer distributions to compute the total delivery time in the models of the OT, OTMD as well as OTOD. The same as random customer distribution, the averages of ten cases are also regarded as the final solutions for the three used customer distribution. In Fig. 7(a) and 7(b), we can found that the improvement of the synchronous delivery efficiency has a close relationship with the distribution of customer nodes. In the single-centered and multiple-centered distributions, the total delivery time is shorter than in the uniform distribution. In our view, the determining factor of this phenomenon is the distribution uniformity of customer nodes. A more uniformly distributed customer will result in a lower ratio between the lengths of the drone and truck routes, as well as the smaller optimal number of drones used in synchronous delivery. Oppositely, if the customer nodes distribute in several areas that have some distances from each other, the routes of drones in the delivery network will lengthen, leading to the increase of the number of serving drones for realizing the shortest truck waiting time.

Fig. 7

For OT, OTMD, and OTOD models, the optimal total delivery times vary with the number of customer in the uniform (a), single-centered (b) as well as multiple centered (c) distributions.

As is demonstrated in Fig. 7(a), similar to the performance of delivery programming in random customer distribution, the optimal total delivery time in OTOD or OTMD model is nearly the half of the one in the OT model for the uniform customer distribution. However, due to the consistency of the distances between two neighboring customer nodes in a uniform distribution, the value of total delivery time in uniform is less than the one at random. In Fig. 7(b), we display the characteristics of the optimal delivery time for the case of single-centered distribution.

Different from the nodes in the uniform distribution, the ones in the single-centered have a high concentration base upon the normal distribution N(0,5), which makes the customer nodes much nonuniform. The distances of customer nodes close to (0,0) are shorter than far away from (0,0). This feature is retained in the averages of 10 single-centered distributed samples, thereby resulting in that the total delivery times in the OTMD and OTOD are less than the half of the one in the OT model, as shown in Fig. 7(b). The improvement of the delivery efficiency for centered distributed customers is more significant than for uniformly distributed. Additionally, comparing the OTMD and OTOD model, it can be found that the former can save 50% total delivery time because of more drones used in the synchronous delivery network. The proposed model is beneficial for the delivery network in terms of centered or nonuniform customer distribution. In Fig. 7(c), similar to the performance of single-centered distribution, the total delivery time with the multiple-centered is also reduced significantly in the OTMD model. However, because two concentration points disperse the customer nodes, the optimal total delivery time with two-centered customer distribution is more unstable than with single-centered.

Finally, with our proposed OTMD model, we plot the optimal numbers of drones as the number of customers in three customer distributions. The distribution of customer nodes has an important impact on the optimal number of drones, as shown in Fig. 8. For the uniform customer distribution, due to the uniformity of the customer nodes, the average number of serving drones is the smallest and around 2 in all the range. For the single-centered distribution, with the increase of numbers of customer nodes, the uniformity of them will deteriorate gradually. Therefore, when the number of customers is small, such as 6,7,8, the optimal number of drones is also stable and around 2, but when the number of customers is large, especially exceeding 9, the optimal number of drones rises significantly. Similarly, for the multiple-centered customer distribution, the number of drones used in the delivery network also has a positive correlation with the number of customer nodes. Nevertheless, due to more concentration points, this number will be more than the one in single-centered customer distribution. These simulated results also agree with our proposed theory that the uniformity of the customer nodes determines the optimal total delivery time and numbers of serving drones.

Fig. 8

The optimal number of drones vary with the number of customers in uniform, single-centered as well as multiple centered distribution with the OTMD model.

6 Conclusion

In this paper, a novel OTMD model of synchronous delivery is proposed in terms of the emerging TSP-D. For obtaining an optimal delivery network that is associated with the total delivery time and the number of drones, we design a united evaluation function to assess the superiority of the logistics network based upon the OTMD model. Regarding this evaluation function as an ultimate objective function, we compute the optimal delivery network by the method of multi-level iterations that corresponds to the calculation of the determined nodes, the truck as well as the drones, respectively. To investigate the characteristics of the optimal solutions on the base of our proposed model and programming method, we compare the results of delivery network programming in the model of OTMD, OTOD, and OT, with four types of customer node distributions. Additionally, the number of drones is also considered as an important factor to study. We found that the uniformity of the customer distributions has a relation with the optimal delivery time and the number of drones. This phenomenon illustrates that the programming model and method can be selected according to the distribution characteristics of the customer nodes, which is very helpful for improving the efficiency of programming the logistics network. In the future work, our investigations will focus on the simplification of OTMD and MTMD. In future research, we will justify the optimization algorithms further, and increase the number of the total nodes to 100 for the research of large scale model.

7 Funding

The authors acknowledge the financial support by “National Natural Science Foundation of China (No. U1833111)”, “Open fund of research institute of air traffic management, China (No. KGYJY2018002)” and “the Fundamental Research Funds for the Central Universities, China (No. 3122018D029).”

References

García-Fernández

, et al., Antenna diagnostics and characterization using unmanned aerial vehicles, IEEE Access 5 (2017), 23563–23575.

Shi

, et al., Multiple Drone-Cell Deployment Analysesand Optimization in Drone Assisted Radio Access Networks, IEEE Access 6 (2018), 12518–12529.

Heath

, The long-range drone that can keep up with a car and fly for an hour, 2015. [Online]. Available: https://www.techrepublic.com/blog/european-technology/the-long-range-dronethat-can-keep-up-with-a-car-and-fly-for-an-hour/.

Bamburry

, Drones: Designed for product delivery, Design Management Review 26(1) (2015), 40–48.

Berg

, On rectilinear link distance, Computational Geometry 1(1) (1991), 13–34.

Goel

and Kok

, Truck Driver Scheduling in the United States, Transportation Sci 46(3) (2012), 317–326.

Glaser

, Watch Amazon’s Prime Air make its first public U.S. drone delivery, 2017. [Online]. Available: https://www.recode.net/2017/3/24/15054884/amazon-prime-air-public-us-dronedelivery.

Brar

, Rabbat

, Raithatha

, Runcie

and Yu

, Drones for deliveries, 2015. [Online]. Available: http://scet.berkeley.edu/wp-content/uploads/ConnCarProjectReport-1.pdf.

Snider

and Welch

W.M.

, FAA shoots down Amazon’s drone delivery plans, 2015. [Online]. Available: https://www.usatoday.com/story/tech/2015/02/15/amazon-cool-to-drone-rules/23473791/

10.

Meola

, The FAA just put up a major roadblock to widespread drone usage, 2016. [Online]. Available: http://www.businessinsider.com/faa-wont-change-airspace-rules-for-drones-until-2016-5.

11.

Paul

, 10 reasons Amazon’s drone delivery plan still won’t fly, 2015. [Online]. Available: http://www.networkworld.com/article2900317/wireless/10-reasons-amazons-drone-delivery-plan-stillwont-fly.html.

12.

Dorr

and Duquette

, Press release – DOT and FAA finalize rules for small unmanned aircraft systems, 2016. [Online]. Available: https://www.faa.gov/news/pressreleases/news_story.cfm?newsId=20515.

13.

McFarland

, U.S. government warms up to drone delivery 2017. [Online]. Available: http://money.cnn.com/2017/10/25/technology/business/drones-trump-local/index.html.

14.

Bonnington

, President trump wants to make drone delivery happen. Don’t expect much (besides crashes), 2017. [Online]. Available: http://www.slate.com/blogs/future_tense/2017/10/27/drone_delivery_isn_t_on_its_way_even_after_president_trump_s_latest_directive.html.

15.

Pugliese

L.D.P.

and Guerriro

, Last-Mile Deliveries by Using Drones and Classical Vehicles, Optimization and Decision Science: Methodologies and Applications 217 (2017), 557–565.

16.

Wohlsen

, The next big thing you missed: Amazon’s delivery drones could work-they just need trucks, 2014. [Online]. Available: https://www.wired.com/2014/06/thenext-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/.

17.

de Freitas

J.C.

and Penna

P.H.V.

, A Randomized Variable Neighborhood Descent Heuristic to Solve the Flying Sidekick Traveling Salesman Problem, Electronic Notes in Discrete Mathematics 66 (2018), 95–102.

18.

Marinelli

, et al., En route truck –drone parcel delivery for optimal vehicle routing strategies,no.4), IET Intelligent Transport Systems 12 (2018), 253–261.

19.

Banker

, The most interesting part of mercedes’ drone-equipped delivery van concept has nothing to do with drones, 2016. [Online]. Available: https://www.forbes.com/sites/.

20.

Crowe

, UPS Delivery Drone Launches from Truck, 2017. [Online]. Available: http://www.roboticstrends.com/article/ups_delivery_drone_launches_from_truck.

21.

Murray

C.C.

and Chu

A.G.

, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transport Res Part C: Emerg Technol 54 (2015), 86–109.

22.

Agatz

, Bouman

and Schmidt

, Optimization Approaches for the Traveling Salesman Problem with Drone, Transportation Sci 52(4) (2018), 965–981.

23.

Q.M.

, Deville

, Pham

Q.D.

and Ha

M.H.

, On the min-cost Traveling Salesman Problem with Drone, Transport Res Part C: Emerg Technol 86 (2018), 597–621.

24.

Es Yurek

and Ozmutlu

H.C.

, A decomposition-based iterative optimization algorithm for traveling salesman problem with drone, Transport Res Part C: Emerg Technol 91 (2018), 249–262.

25.

Wang

, Poikonen

and Golden

, The vehicle routing problem with drones: Several worst-case results, Optim Lett 11(4) (2017), 679–697.

26.

Ham

A.M.

, Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming, Transport Res Part C: Emerg Technol 91 (2018), 1–14.

27.

Kitjacharoenchai

, Ventresca

, Moshref-Javadi

, Lee

, Tanchoco

Jose M.A.

and Brunese

P.A.

, Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers & Industrial Engineering 129 (2019), 14–30.

28.

Wang

and Sheu

J.B.

, Vehicle routing problem with drones, Transport Res Part B: Meth 122 (2019), 350–364.