Drone delivery has been attracting attention, and many companies are focusing on this as a means to solve logistics issues. In order to deliver packages by drone, it is necessary to optimize the route in advance. So far, drone routing problems that consider changes in flight speed due to load have been proposed. This routing problem is called the FSVRP. An Integer Linear Programming (ILP) approach to the FSVRP was proposed in the past. In this paper, to obtain a more accurate solution than the ILP approach, we propose an Integer Quadratic Programming (IQP) approach. Experiments show that the proposed method is effective compared to stateof-the-art methods.
The 4th International Symposium on Advanced Technologies and Applications in the Internet of Things (ATAIT 2022), August 24-26, 2022, Ibaraki, Japan function of the original FSVRP is not linear but very complex. The work in [10] linearizes the objective function by the least-squares approximation method at the cost of degraded accuracy.
This paper proposes an integer quadratic programming (IQP) approach to FSVRP. The objective function of this work is more accurate than the one in [10], and thus, this work can find better routes.
The rest of this paper is organized as follows. Section 2 describes the FSVRP. Section 3 describes an IQP approach to the FSVRP. Section 4 shows the experimental evaluation. Finally, Section 5 concludes this paper.
This section describes FSVRP (flight-speed aware vehicle routing problem) presented in [6] and [10]. FSVRP is a variation of routing problems for delivery drones that accounts for flight speed as a function of load. The FSVRP is the problem of finding a route that minimizes the time taken to deliver all parcels to their respective customers and back to the depot. The problem which we are concentrating on requires the shortest route in terms of flight time, taking into account the speed of flight as a function of the load. 2.1.
As an example, we depict Figure 1. The node labeled "0" is the depot and the other nodes are the customers. The number in the box indicates the weight of the parcel to be delivered to the customer. The red number on the sides is the distance between the two customers or a depot and a customer. Drones can ignore geographical constraints since the drones can fly, and the drones can visit any customer. Figure 1, if we minimize the total flight distance, this problem is typically solved as a traveling salesman problem. In figure 2, the route shown by the arrow is obtained as the optimal route. The total flight distance of the shortest route in the TSP is 146 (= 43 + 52 + 24 + 27). The total flight time of this TSP optimal route is 102 (= 36 + 36 + 15 + 15) unit of time in Figure 2 (b). This route is the optimal route in terms of the total flight distance. If the flight speed is fixed, the shortest route is optimal in terms of both flight distance and flight time. However, the heavier the load, the slower the drone flies, and the lighter the load, the faster the drone flies. In figure 3, the route shown by the arrows is obtained as the shortest route in terms of flight time, and the shortest route is determined by two factors: the weight of the load and the distance. The total flight distance of the FSVRP-optimal route is 146 (= 27 + 24 + 52 + 43), which is the same as the TSP optimal route. The total flight time of the FSVRP optimal route equals the total flight time of that TSP optimal route, but in general, the total flight time of the FSVRP equals or exceeds the total flight time of the TSP. However, the total flight time of the FSVRP-optimal route is 93 (= 21 + 15 + 33 + 24), which is shorter than the TSP optimal route. In Figure 2, the drone has all the parcels at the depot, and its total weight is 127. It starts delivery with a total weight of 127 and delivers the load to customer 2, whose load is 43. The remaining parcels with a total weight of 84 are then delivered to each customer. In Figure 3, the drone starts the delivery with 127 (units of weight) and delivers the heaviest parcel with a load of 50 to customer 1. It then delivers the remaining parcels with a total weight of 77 to each customer. Then, the drone can fly faster during the rest of the delivery. As shown by this arrow, in the FSVRP with drones, there are cases where it is better to carry the heavy load first, because the drone's flight speed is highly dependent on the load. 2.2.
In this problem, there are N customers to be delivered. To avoid loss of generality, a drone delivers
only one parcel per customer. Therefore, the number of parcels is N. The customers are numbered from
1 to N. The parcel to be delivered to customer (
In this paper, the drone delivers all parcels to customers in a single delivery. All the parcels are uploaded onto the drone at the depot, which is the delivery base, and the drone begins the delivery. If the total weight of the parcels to be delivered exceeds the maximum payload of the drone, the parcels must be partitioned into multiple groups and delivered multiple times before delivery, which is not considered in this paper.
To begin with 1, 2 represents the distance between points 1 and 2. Also, is the decision
variable in the routing problem and indicates the -th customer to visit. The equation (
The drone visits every customer only once. This is defined as follows: 0 1
0
1
,
,
(
1 / Min , 1 /
Besides, 1, 2 represents the time it takes for the drone to fly between points 1 and 2. Note that
is a function of the load. This equation (
The equation (
(a) Fight without payload
(b) Flight with payload
When the drone arrives at the -th stop (
The flight speed of a drone is also greatly affected by the weight of the parcel it is carrying, wind,
and other factors. When a drone flies, it tilts its fuselage. in the equations (
The equations (
From the above, and can be expressed as the equations (12) and (13).
cos
sin
arccos
arccos
/
/
(
Section 3 explains how the problem presented in Section 2 is solved using the IP solver. IP solvers, like CPLEX and Gurobi, utilize a combination of a variety of heuristics on their own to quickly find a solution. Furthermore, many solvers are frequently built to work on multicores. As a result, solvers are able to solve a variety of problems more quickly than an algorithm designed by programmers who are not algorithmic experts. As the objective of the problem in Section 2 is not linearized and included trigonometric functions, it is not possible to solve the problem with ordinary IP solvers. This section provides an approximated objective by quadratic approximation to solve the problem using an IP solver.
Based on Section 2, we can obtain equation (14), which is a sort of approximation, but it is still too complex to be solved as an integer programming.
1/ 1/ sin arc cos
/ sin arc cos / The equation (15), which is the reciprocal of the flight speed, is used for the objective of the FSVRP.
The vertical axis in figure 5 is the reciprocal of the flight speed, and the horizontal axis is the weight of loads delivered by the drone. Currently, drones are being developed to carry cargo, and the weights of the cargo that drones can carry vary. In this figure, the maximum payload a drone can carry is based on SkyLift [11]. SkyLift is the name of the cargo drone. The literature in [11] states that the maximum payload of this cargo drone is 30 kg, but we experimented with a maximum payload of 27 kg to give ourselves a margin of 10%. The total weight of the parcels are determined in the range of 0 27000. For the black curve, a quadratic approximation using the least-squares method gets a red curve in the figure. The R-squared value, which is the error from equation (16) due to the approximation, is 0.9647.
1/ 3 10 3 10
Substituting equation (16) into the expression for velocity in equation (
The effectiveness of our proposal is evaluated through experiments. Six routing algorithms shown below are compared in terms of total flight time and the runtime of the algorithms.
DP-FSVRP: Solve the FSVRP by dynamic programming. It calculates the route that minimizes the total flight time.
DP-TSP: Solve the TSP by dynamic programming. It calculates the route that minimizes the total flight distance.
CPLEX-ILP-single: Solve the linearized FSVRP with CPLEX on a single thread.
CPLEX-ILP-multi: Solve the linearized FSVRP with CPLEX on multiple threads.
CPLEX-IQP-single: Solve the FSVRP based on an IQP approach with CPLEX on a single thread. This is our proposal.
CPLEX-IQP-multi: Solve the FSVRP based on an IQP approach with CPLEX on multiple threads. This is also our proposal.
In our experiments, we have prepared five problem instances for each method with 5 to 20 customers, which are randomly generated. We set the runtime limited up to 3600 seconds in wall-clock time. The experiments are conducted on AMD Ryzen 7 PRO 4750G (8 cores, 16 threads) and 64GB of main memory. In addition, to compute the solution, we used Python 3.8.5 for the existing method and IBM ILOG CPLEX Optimization Studio 20.1 for the proposed method. 4.1.
In Figure 6, it shows comparison in terms of runtime of each method using a logarithmic scale. The vertical axis is runtime, and the horizontal axis is the number of customers. The optimal solutions of CPLEX-IQP-single and CPLEX-IQP-multi can be found because it takes so much runtime to compute a quadratic function. From 5 to 16 customers, DP-FSVRP is the fastest in finding the optimal route compared to other algorithms since CPLEX incurs the overheads by generating the model and parallelizing it into multiple threads. We think that the reason why there are variations of the solution time of CPLEX is because the number of instances is as small as 5. More than the number of customers 17, there are cases in which CPLEX-ILP can require to solve faster than DP-FSVRP. Due to the multithreaded execution, CPLEX-ILP-multi and CPLEX-IQP-multi can achieve shorter runtime than CPLEX-single. These results show that linear approximations can be solved faster than quadratic approximations. Since the runtime of CPLEX-IQP is about 1 minute for up to the number of customers 9, we do not consider this to be a particular problem in practical use.
This paper presented an IQP approach to delivery drone routing under load-dependent flight speed. Up to the number of customers 9, the runtime of CPLEX-IQP is at most 1 minute, and since CPEXIQP provides a better solution than CPLEX-ILP, we think that our proposed method is useful in practical use. We also think that CPLEX-IQP is superior to dynamic programming for FSVRP based on the fact that IP solvers can easily extend the problem. In the future, we will take into account multiple deliveries to routing problems of a drone considering load-dependent flight speed.
This work is partly supported by JSPS KAKENHI 19H04081, 20H00590 and 21K19776.