Delivery drones have been attracting attention as a promising means of package delivery. However, drones are subject to various factors that a ect their ight speed compared to traditional trucks. In past researches, Flight Speed-aware Vehicle Routing Problem (FSVRP) was studied. The FSVRP addresses the problem of minimizing the total ight distance. It was studied considering the e ect of the ight speed due to the weight of the cargo. However, the ight speed of drones varies with the wind as well as the load. In this paper, we de ne Flight Speed-aware Vehicle Routing Problem with the Wind (FSVRPW) for ight distance minimization. We also propose an algorithm to solve the FSVRPW accurately and quickly. The metrics of ight distance, ight time, and running time are compared with the conventional FSVRP.
1 Ritsumeikan University 2 JSPS Research Fellow 3 Osaka University
In recent years, drones have been used for a variety of purposes due to their lightweight frames and improved battery capacity. Among them, drone-based delivery services have been attracting attention. Drones are considered a promising means of delivery service because they are not a ected by road tra c conditions. It also has the advantage of lower CO2 emissions and labor costs compared to truck-based package delivery. Drones deliver packages automatically, so there is no human work involved in the delivery process. On the other hand, drones cannot y long distances since they are battery-powered. Therefore, it is necessary to consider what is the best order to increase the number of packages carried by the drone. The truck delivery routing problem has been the subject of much research. However, it is di cult to apply these researches to drones because the considerations for delivery are di erent between trucks and drones. Therefore, it is important to study delivery routing problems that take into account the characteristics of drones.
The delivery drones routing problems have been the subject of much research [
In this paper, we address the Vehicle Routing Problem (VRP) for package delivery drones and address the delivery routing problem of minimizing the ight distance considering the change in ight speed due to load and wind. This paper is the rst delivery drone routing problem that considers the change in ight speed due to load and wind. In this paper, given a set of package to deliver and wind velocity, the problem tries to nd an optimal route that starts from a depot, delivers all of the packages to customers, and comes back to the depot with the e ect of wind in mind. To solve FSVRPW, the paper presents a dynamic programming algorithm. Dynamic programming algorithm e ciently nds exactly optimal routes in terms of total ight distance.
The rest of this paper is organized as follows. Section II surveys related work. Section III describes the routing problem for delivery drones. Section IV proposes a dynamic programming algorithm for the FSVRPW. Section V presents evaluation and nally, Section VI concludes this paper. 2
Delivery drone routing problems is studied a lot [
Delivery drone routing problems are studied a lot [
There are several studies aimed at minimizing the energy consumption[
This section describes FSVRP as proposed by Funabashi et al.[
A variety of methods have been studied for drone delivery planning. However, most of the studies did not consider the e ect of wind when determining the order of delivery. Therefore, it is necessary to consider wind in the delivery planning stage. In this paper, we extend the FSVRP proposed by Funabashi as a base. FSVRP is working on a delivery plan that minimizes the ight time when the ight speed is a ected by the weight of the load.
We explain the di erence between FSVRP and FSVRPW using a concrete example. The map used in the concrete example is shown in Figure 1a. It shows the distance between each customer and the weight of the package to be delivered to each customer when the number of customers is 3.
Depot 0 20 21 25 20 1 32.6 3 18
41 Wind Vector 32 2 5
Weight
20 Depot 0
The distance between each customer is shown in red, and the weight of the package to be delivered to each customer is shown in the square box. The example also assumes that the wind is blowing from customer 2 towards the delivery base. The FSVRP changes its ight speed depending on the weight of the load. Speci cally, when the payload is heavy, the speed becomes slower, and when the payload is small, the speed becomes faster. In FSVRPW, the ight speed of drones is changed due to load and wind.
The concrete examples of FSVRP and FSVRPW are shown in Figure 1. FSVRP route is shown in Figure 1b. The delivery order written in the red line is the delivery order in which the ight time calculated by FSVRP is minimized. The ight time of the drone depends not only on the ight distance but also on the total weight of the payload. The heavier the load, the slower the ight speed and the longer the ight time. This implies that heavier loads should be given priority for delivery. Therefore, the optimal ight distance for FSVRP is 104:6 (20 + 32:6 + 32 + 20), and the ight time is 606:2 (431:5 + 56:3 + 48:0 + 70:4). However, this is not the optimal delivery order in FSVRPW. FSVRPW route is shown in Figure 1c. It's not only the load that a ects the ight speed of the drone, but also the wind. When delivering a heavy load in a headwind, the ight speed is most a ected. The slower ight speed will also increase the ight time. This means that priority should be given to delivering heavy loads with a tailwind. The overall ight time can also be minimized by giving priority to lighter loads if they are in a tailwind. Therefore, the optimal ight distance for FSVRPW is 118.6 (25+32.6+41+20), and the ight time is 417.9 (144.9+152.9+49.7+70.4). As can be seen from this result, it is necessary to consider not only the total weight of the payload but also the wind in the delivery routing. 3.2
This section is about the description and formulation of FSVRP and FSVRPW. The FSVRP
dealt with in this paper is based on [
We are given N items to deliver. To avoid lost generality, we do not deliver more than two packages to the same customer. In other words, multiple packages to the same customer are combined in advance. Also, the number of customers is N , and packages are numbered from 1 to N . The customer to whom package i (1 i N ) is delivered is called customer i or point i, and the depot is numbered 0, as shown in the example in Figure 1. In this paper, we assume that all packages are delivered at one time. Also, all the packages are loaded onto the drone at the depot, and the delivery is started. If the total weight of the packages exceeds the carrying capacity of the drone, the packages need to be divided, which is out of the scope of this paper. Let d(i1; i2) denote the distance between customers i1 and i2. Also, let x(j) denote the j-th visited customer, which is the decision variable of the routing problem. Since a route starts and ends at the depot, we de ne: (1) (2) (3) (4) (5) (6) (7) Let t(i1; i2) denote the ight time between customer i1 and i2. The drone ight time from i1 to i2 is given by the distance between i1 and i2 divided by the drone ight speed v. Note that v is a function of payload. Therefore, the ight time between customers j-th visited and (j + 1)-th visited is de ned as:
t(x(j); x(j + 1)) = d(x(j); x(j + 1))=v(W (j)) The FSVRP asks the shortest ight time in all ight routes, and its objective function is de ned as: When the drone makes the j-th stop (1 j N ) at customer x(j), a package of weight w(x(j)) is unloaded. Therefore, the total payload when the drone leaves customer x(j) is de ned as: The FSVRP addressed in this paper is formally de ned as follows. Given w, d and v, nd x which minimizes the objective function (7) while meeting the constraints (1)-(6).
In FSVRPW, the e ect of wind is added to the velocity used in FSVRP. If the wind speed is vw, equation (6) is de ned as:
t(x(j); x(j + 1)) = d(x(j); x(j + 1))=vd(W (j); vw) Therefore The FSVRPW asks the shortest ight time in all ight routes, and its objective function is de ned as: The FSVRP addressed in this paper is formally de ned as follows. Given w, d, v and vw x which minimizes the objective function (9) while meeting the constraints (1)-(5),(8). 3.3
In the problem de ned above, the ight speed function v is speci c to the drone. We assume that v is assumed to be given, and how to accurately obtain v is out of the scope of this paper. Instead, the rest of this section only provides a simple approximation of how the load and wind of the drone a ect the ight speed v. (8) (9) nd (10) (11) " ! # (a) Drone without load #" !"
" ($ + ) (b) Drone with load w The horizontal component of P , i.e., Px, is the power towards the destination, and is equal to the air resistance k v(0) where k is a drone-speci c coe cient.
Px = P sin( ) = k v(0) % (16) (17) (18) Hence, we derive: " # " ! !
Py0 = P cos( 0) = (Wd + w) g
Px0 = P sin( 0) = k v(w) v(w) = sin( 0) = sin( 0) sin( )
v(0) 0 = arccos( (Wd + w) g
P
) = arccos(
Wd g
P
) P k $ #(#)
" # # $
#cos(#) ! !cos(!) ! !sin(! ) (a) Situation settings
(b) Speed after e ect with the wind
Next, we consider the e ect of the wind in the direction of travel of the drone. Let vw denote the wind velocity and vd denote the drone velocity. From the angle formed by the wind and the customer, we de ne as: The norm of the synthetic vector v0 of vw and vd can be expressed as follows: jvwj sin( w) = jvdj sin( d) jv0j = jv0j cos w + jvdj cos d According to Formula (17) and (18), the scalar of the vector v0 is led in the following formula: jv0j = jvwj cos( w) + jvdj cos(arcsin( jvwj sin( w) )) jvdj Algorithm 1 Dynamic Programming for FSVRPW
This section proposes an exact algorithm for the FSVRPW de ned in the previous section. The
proposed algorithm is based on dynamic programming [
Let S denote a set of customers who are already visited, and let i be the last-visited customer in S. We call a pair (S; i) as a state. Obviously, the initial state is (f0g; 0). Then, we de ne a problem asking the minimum ight time T (S; i) for delivery from the initial state to state (S; i). Now, we can derive a recurrence formula to calculate T (S; i) as follows.
T (S; i) = minf T (Sni; i0) + t(W 0(S) + w(i); d(i0; i); vw)j i0 2 Sni g Recall that i is the latest customer in S. In the formula, i0 denotes the second latest customer. T (Sni; i0) is the minimum ight time for ying from the depot to i0, and t(W 0(S) + w(i); d(i0; i)) is the ight time for ying from i0 to i. W 0(S) denotes the total weight of items which are not yet delivered, which is formulated as: In Formula (20), it should be noted that, when departing from i0, item i is still loaded on the drone. Therefore, w(i) is added to W 0(S). Also, it is obvious that the ight time at the initial state, i.e., before leaving the depot, is zero.
The original routing problem asks the minimum ight time when the drone departs from the depot, visit all of N destinations, and comes back to the depot. Formally, the original problem asks:
T (f0; 1; 2; :::; N; 0g; 0)
W 0(S) =
X w(k) k2=S T (f0g; 0) = 0 (20) (21) (22) (23) The problem in Expression (23) is recursively partitioned into sub-problems according to Formula (20), reaching Formula (22), and then, the optimal route with the shortest delivery time is obtained.
Winit is the total weight of all items to be delivered, and V is a set of customers. state
represents a set of customers who are already visited. Actually, state is a bit-vector of length
N , where N is the number of customers. If customer i is visited, the (i 1)-th bit is set.
dp[state][customer] is a two-dimensional array which stores the ight time, and it corresponds
to T (S; i) in the previous section. For example, dp[
The e ectiveness of our proposed FSVRP is evaluated through experiments. We implemented several routing algorithms in Python, and are compared in terms of the runtime of the algorithms, total ight time, and the total ight distance. 5.1
Four routing algorithms shown below are compared in the experiments.
• FS-BF : A brute-force algorithm for FSVRP. It exhaustively explores all possible routes
(i.e., N! routes) to nd the one with minimum ight time.
• FS-DP : Dynamic programing algorithm for FSVRP [
• FSW-DP : Our DP algorithm proposed in Section 4 for FSVRPW.
In our experiments, we have prepared 20 test cases for each method with 5 20 customers each. The ight distance, ight time, and execution time are calculated from the average of the 20 patterns. The wind strength is tested at 25% and 50% of the drone's speed. We also set the running time limit to 3600 seconds. 5.2
Figure 4 shows the ight distance for each method at 25% and 50% wind, normalized by DPFS. The experimental results show that the proposed method has a long ight distance for all customer numbers compared to DP-FS. When comparing DP-FSW-0.25 and DP-FS-0.25, the ight time was reduced by 8.89% on average. The average ight distance increased by 8.89% when compared to DP-FSW-0.25 and DP-FS-0.25, and by 39.37% when compared to DP-FSW-0.5 and DP-FS-0.5. Next, Figure 5 shows the ight time for each method at 25% and 50% wind, normalized by DP-fs. The experimental results show that the proposed method has a short ight time for all customers compared to DP-fs. When comparing DP-FSW-0.25 and DP-FS-0.25, the ight time was reduced by 0.56% on average. The average ight time was 0.56% shorter when comparing DP-FSW-0.25 and DP-FS-0.25, and 23.45% shorter when comparing DP-FSW-0.5 and DP-FS-0.5. These results show that even if the ight distance is longer, delivery can be made in a shorter time by using the wind. Next, Figure 6 shows the 1.6 1.4 e1.2 m i tT 1 h g li0.8 F d lize0.6 am0.4 r o N0.2
0 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Number of Customers 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Number of Coustomers computation time for each method. From the results of the experiments, the computation time for BF-FSW-0.25 and BF-FSW-0.5 exceeds one hour when the number of customers exceeds 12, making it impossible to determine the delivery route. On the other hand, DP-FSW-0.25 and DP-FSW-0.5 were able to perform the calculation for all customers within one hour. From the above results, our proposed algorithm can show its usefulness when the number of customers is 20. 6
Drones are expected to be popular vehicles for delivery services. In this paper, a dynamic programming algorithm is proposed de ning vehicle routing problems that take into account 1000 100 )(se 10 igTm 1 n innu 0.1 R 0.01 0.001 5 7 9 the changes in ight speed due to load and wind. Experimental results show the e ectiveness of the proposed algorithm. In future work, we are considering the e ect of dynamically varying wind on the ight speed.