# Drone Delivery Vehicle Routing Problem with Multi-flight Level

Yonggab Kim, Hoyoung Jung, Seokcheon Lee

► To cite this version:

Yonggab Kim, Hoyoung Jung, Seokcheon Lee. Drone Delivery Vehicle Routing Problem with Multi-flight Level. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.43-51, 10.1007/978-3-030-85906-0_5 . hal-04022113

HAL Id: hal-04022113

https://inria.hal.science/hal-04022113

Submitted on 9 Mar 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Drone Delivery Vehicle Routing Problem with Multi-flight Level

Yonggab Kim¹[0000-0001-9289-3261], Hoyoung Jung¹[0000-0002-9830-6555], and Seok-cheon Lee¹[0000-0002-2019-1129]

¹ Purdue University, West Lafayette IN 47906, USA

**Abstract.** The advantage of drone delivery is that it can efficiently use the vertical space in the air, allowing multiple operations at different flight levels. However, flight level and delivery efficiency come at a tradeoff, especially in a metropolitan area with many skyscrapers; placing drones higher requires more time, but the higher they are, the less detour they make due to the smaller number of buildings at higher altitudes, resulting reduced time in routing. This study integrates the problem by dividing the heights and identifying buildings that could possibly be an obstacle. We propose a novel vehicle routing problem for multi-flight level drone delivery to minimize delivery completed time.

**Keywords:** Drone Delivery, Vehicle Routing Problem, Multiple Flights, Logistics

## 1 Introduction

The desire for a faster and less expensive last-mile delivery service has always been present in the retail industry. The cutting-edge technology of unmanned aerial vehicles (UAVs), commonly known as drones, provides a new advanced option to the retail industry to fulfill its demand. Especially after the outbreak of COVID-19, drone delivery is an attractive choice to avoid human contact and help in handling the COVID-19 pandemic [1].

Many companies have already developed their drone delivery business. Amazon is the biggest player in the market; they have announced their Prime Air service. [2]. In 2020, Amazon won an approval from the FAA (Federal Aviation Administration) for their prime air drone delivery fleet [3]. Alphabet is another big company testing their drone delivery service in Australia by their project Wing [4]. Other retail companies such as UPS, Walmart, and Tesco are also investing in the drone delivery business.

The contributions of this study are as follows. First, we proposed a new optimization problem with multiple flight levels in drone delivery. To the best of our knowledge, this is the first paper that takes account of the optimal flight level in the drone delivery problem. The second contribution is that we examine the advantage of operating drone service with New York City's real-world data. Lastly, we suggest a new heuristic algorithm with capacity in drone delivery.

The rest of this paper is organized as follows. In section 2, we review the relevant literature on the drone delivery problem. Section 3 defines the problem statement and suggests the mathematical. Section 4 presents a new solution algorithm, MFLSA, which is named after multi-flight level solution algorithm. This algorithm aims to solve to solve the complex model in a timely manner. Section 5 test this algorithm to the real
data-based case study on New York City. The experiment result and data analysis are presented in section 6. We conclude this paper with a suggestion and potential future research.

## 2 Literature Review

The initial studies in the drone routing problem have been focused on the disaster situation or military applications. A group of studies has investigated the drone routing problems in information gathering and disaster control at catastrophe situations and surveillance monitoring [5]-[7]. As the energy efficiency and the payload capability of drone increased over several years, using the drones for the last mile delivery have gained attention in logistic field. One study introduced FSTSP, which studies the routing challenge of a drone assisting a delivery truck for last-mile delivery [8]. Researchers have used a mixed-integer linear programming (MILP) formulation and simple heuristics for a solution. Further research has been done to extend the FSTSP considering no-fly zones and using local search heuristics as a solution approach [9].

Other researchers have investigated a similar problem, the traveling salesman problem with the drone. (TSP-D) Compared to FSTSP, this study allows the drones to return to the original place where the drone has departed [10]. To solve the TSP-D, solution approaches of mixed-integer programming, heuristics, and dynamic programming were introduced [11],[12]. Furthermore, utilizing multiple drones, multiple of vehicles, and heterogeneous UAVs that have different properties were studied [13]-[15].

Consideration of cost, battery constraints, weights, and other important factors of drone has been by the researchers. While the drone has many advantages over conventional transportations, reduced energy capacity and lower payload weight is the major concern for drone delivery system. Battery management using efficient battery assignment and battery scheduling was studied to reduce the average waiting time and energy cost [16]. Another study considers the relationship between payload weight and energy consumption to remove the infeasible routes and construct cost-efficient route [17]. The authors use simulated annealing to find the solution in different scenarios.

## 3 Problem statement and mathematical model formulation

In this section, we define the capacitated drone delivery problem with multiple flight levels and propose a novel mathematical formulation to minimize the completed time while utilizing multiple flight levels and meeting the capacity constraints.

### 3.1 Problem Statement

* The delivery is made from a depot to one customer and then returns to the original depot.

* There are multiple flight levels drones can choose to fly to deliver.
* Customer demands are represented as weights, and all the demands need to be fulfilled.

* Depot has the capacity in weights and can have multiple drones.

* Drones have the weight capacity that they can carry in a single flight.

* Our goal is to minimize the completed time after serving all the customers.

## 3.2 Mathematical Formulation

<table><caption>**Table 1.** System Variables</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td colspan="3"><strong>Sets</strong></td></tr><tr><td><em>U</em></td><td>:</td><td>Sets of UAVs</td></tr><tr><td><em>C</em></td><td>:</td><td>Sets of customers</td></tr><tr><td><em>D</em></td><td>:</td><td>Sets of depots</td></tr><tr><td><em>F</em></td><td>:</td><td>Sets of flights</td></tr><tr><td><em>W</em></td><td>:</td><td>Sets of Weights</td></tr><tr><td><em>L</em></td><td>:</td><td>Sets of levels</td></tr><tr><td colspan="3"><strong>Parameters</strong></td></tr><tr><td><em>Ini</em><sub><em>u</em></sub></td><td>:</td><td>Initial location of UAV <em>u</em></td></tr><tr><td><em>τ</em><sub><em>i,j,l</em></sub></td><td>:</td><td>Distance between <em>i</em> and <em>j</em> at level <em>l</em></td></tr><tr><td><em>P</em><sup><em>w</em></sup><sub><em>i,j,l</em></sub></td><td>:</td><td>Energy Consumption from <em>i</em> to <em>j</em> on level <em>l</em> of weight <em>W</em></td></tr><tr><td><em>φ</em><sub><em>l</em></sub></td><td>:</td><td>Downtime for drone for level <em>l</em></td></tr><tr><td><em>ψ</em><sub><em>l</em></sub></td><td>:</td><td>Uptime for drone for level <em>l</em></td></tr><tr><td><em>Capacity</em><sub><em>d</em></sub></td><td>:</td><td>Depot Capacity for depot <em>d</em></td></tr><tr><td><em>Demand</em><sub><em>c</em></sub></td><td>:</td><td>Customer Demand for customer <em>c</em></td></tr><tr><td><em>E</em></td><td>:</td><td>Energy capacity of the drone</td></tr><tr><td><em>V</em></td><td>:</td><td>Drone speed</td></tr><tr><td colspan="3"><strong>Decision variables</strong></td></tr><tr><td><em>x</em><sup><em>u</em></sup><sub><em>i,c,w,f</em></sub></td><td>:</td><td>Binary decision variable, If the UAV <em>u</em> is departing from <em>i</em> to <em>j</em> a level <em>l</em> of a weight <em>W</em> on flight <em>f</em></td></tr><tr><td><em>T</em><sup><em>u</em></sup></td><td>:</td><td>Current Time of UAV <em>u</em></td></tr></tbody></table>

<table><caption>**Table 2.** Mathematical model</caption><tr><td colspan="3"><strong>Mixed integer linear programming</strong></td></tr><tr><td>Minimize</td><td><em>O</em></td><td>(1)</td></tr><tr><td>Subject to</td><td><em>O</em> ≥ <em>T</em><sup><em>u</em></sup> ∀<em>u</em> ∈ <em>U</em></td><td>(2)</td></tr></table>
$$ \sum_{w \in W} \sum_{l \in L} \sum_{c \in C} x_{u,c,w,f}^{u} \leq 1 \quad \forall f \in F \qquad (3) $$

$$ \text{Demand}_{c} \leq \sum_{w \in W} \sum_{l \in L} \sum_{c \in C} \sum_{u \in U} w \cdot x_{l,c,w,f}^{u} \quad \forall c \in C \qquad (4) $$

$$ x_{l,u,c,w,f}^{u} \cdot \sum_{w \in W} \sum_{l \in L} \sum_{c \in C} \sum_{u \in U} (2 \cdot \tau_{l, \text{Ini}_u, c} / v + \psi_l + \phi_l) \leq T^u \qquad (5) $$

$$ x_{l,u,c,w,f}^{u} \cdot (Pij_{l, \text{Ini}_u, j}^{w} + Pij_{l, \text{Ini}_u, j}^{0}) \leq E \qquad (6) $$

$$ \sum_{w \in W} \sum_{l \in L} \sum_{c \in C} \sum_{u \in U} \sum_{f \in F} w \cdot x_{l,c,w,f}^{u} \leq \text{Capacity}_{d} \quad \forall d \in D, \text{Ini}_{u} = d \qquad (7) $$

Table 1 is the variables that is used for constructing the mathematical model. Table 2 is the equations to solve the minimization problem suggested in this paper. Equations (1) and (2) are the objective function. The objective function minimizes the completed time after serving all the customers. Equation (3) is the constraint that ensures the drone delivery is made to the customer once or less in a single flight. Constraint (4) prevents the sum of the delivery weight fulfills the amount of weight of customer demand. Constraint (5) calculates the completed time of each drone after serving all the customers. Constraint (6) restricts the round trip that exceeds the drone energy capacity is not being made. Lastly, constraint (7) guarantees the total delivered weight of drones from the same depot does not exceed the sum of depot capacity.

# 4 MFLSA

The MFLSA is a new heuristic algorithm for drone vehicle routing problem that considers the multiple flight levels using local search approach.

## 4.1 Initial Solution Generation

The algorithm starts by generating the initial population (see Fig. 1). The first initial solution is generated by the Nearest Neighbor algorithm, and the part of the solution was generated based on the first initial solution. The other solutions were generated randomly. In this problem, when all initial solution was created randomly, too many unfeasible solutions were produced because of capacity constraints. Inserting feasible solutions created by heuristics to the randomly generated solutions led the genetic algorithm to yield a good portion of feasible solutions [18]. The optimal flight level for each flight is calculated when the destination route is given by chromosome.

## 4.2 Selection

The selection strategy decides which individuals are passed off from the parents to the offspring. This research adopts two selection schemes, elitist selection, and proportional roulette wheel selection. The elitist selection picks individuals with good fitness.
This allows the algorithm to preserve the best solution from parents to the offspring. In a proportional roulette wheel selection scheme, individuals are chosen with a probability that corresponds to their proportion of fitness value over the sum of all fitness values. The proportional roulette wheel gives all the individuals a chance to be selected and maintained their diversity [19].

<figure><img src="image_3.png" /><figcaption>Fig. 1. Flowchart of the MFLSA</figcaption></figure>

## 4.3 Local Search Heuristics

In a search phase, several search heuristics are used to improve the selected individuals. Two index points, I and J are randomly selected from the total length of the chromosome. The 2-opt operator selects parts from I to J and reverses the order of the index from the selected part. The swap operator exchanges the I point route and J point route. The insertion operator moves the route at the I point of the chromosome to J point. The
cross-move operator interchanges the part of the chromosome between I to J and replaces the repeated route with the value outside of I and J.

## 5 Case Study

In this section, we try to validate our proposed mathematical model and algorithms to a real case study in New York City. New York City is known to be the place where it has the most skyscrapers in North America. In 2020, NYC held 35% (90/255) of all North America's 200 m + buildings [20]. Many tall buildings in the New York City area become more obstacles for drones to avoid.

The data used for this case study is collected from NYC open data, which contains data about building footprints and building height. The data was published in 2016 and is being updated weekly. We selected the midtown area of Manhattan created a heatmap by using ArcGIS (see Fig. 2). The heatmap color represents buildings over a certain height. The yellow, orange, and red color represents the buildings over 50m, 100m, and 150m, respectively.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Google New York city map and height heat map</figcaption></figure>

The heatmap was divided into three maps representing different heights by OpenCV library. A* Algorithm was used to route from depot to customer. The UAV that is selected for this research is DJI Matrice 300 RTK.

## 6 Computational Result and Conclusion

In this section, we discuss the result we have obtained by running a series of numerical experiments. The number of customers was set to 20. The number of depots was set to 4, and the location was generated randomly, having 2 drones at each depot. The drones can deliver the weights between 1-2 Kg to the customer. To validate the result, 20 different scenarios were generated and tested. All the algorithms are coded in Python, and experiments were run on an HP Laptop 15t-dc100 2.6 GHz processor with 16GB of RAM.
## 6.1 Performance comparison

To evaluate the performance of the MFLSA, MILP model, GA, SA, and Nearest neighbor algorithm was also tested. The objective value is the completed time after serving all the delivery, and the lower the value is the better. Table 1 is summarizing the comparison between the algorithms.

<table><caption>Table 3. Performance Comparison Table</caption><thead><tr><th></th><th>MILP</th><th>MFLSA</th><th>GA</th><th>SA</th><th>Nearest Neighbor</th></tr></thead><tbody><tr><td>Objective Value</td><td>870</td><td>966.7</td><td>1010.94</td><td>1074.83</td><td>1092.25</td></tr><tr><td>Computation Time (Seconds)</td><td>2578.97</td><td>193.69</td><td>198.83</td><td>194.21</td><td>0.06</td></tr></tbody></table>

MILP shows the optimal objective solution of 870, compared to other algorithms but shows a longer computation time, 2578.94. This makes the mathematical model hard to apply in the real world. On the other hand, the Nearest Neighbor algorithm shows fast computation time, 0.06 but the solution is far from the optimal solution compared to other algorithms. The suggested algorithm, MFLSA shows a near-optimal solution and similar computation time compared to GA and SA. MFLSA provides the high quality of solution in a reasonable time. (see Fig. 3).

<figure><img src="image_5.png" /><figcaption>Fig. 3. Algorithm comparison bar graph</figcaption></figure>
## 6.2 Conclusion

To take one step closer to drone delivery commercialization, some of the essential real-world life challenges should be addressed in advance. This research considered the optimal height level for drones to operate in a metropolitan area. A mathematical model and heuristic algorithm were developed to optimize the completed time after serving all the delivery. To test our model, we have done a case study in New York City and compared the result of the outcome.

## References

1. Kumar, A., Sharma, K., Singh, H., Naugriya, S. G., Gill, S. S., Buyya, R.: A drone-based networked system and methods for combating coronavirus disease (COVID-19) pandemic. Future Gener. Comput. Syst., vol. 115, pp. 1–19, (2020). doi: 10.1016/j.future

2. Amazon Prime Homepage, https://amzn.to/3t93se9, last accessed 2021/4/10.

3. CNBC News, https://cnb.cx/2PSUWl1, last accessed 2021/4/8.

4. Wing Homepage, https://wing.com/, last accessed 2021/4/7.

5. Frew, E. W., Brown, T. X.: Networking issues for small unmanned aircraft systems. Unmanned Aircraft Syst., pp. 21–37 (2009).

6. Curry, J. A., Maslanik, J., Holland, G., Pinto, J., Tyrrell, G., Inoue, J.: Applications of aero-sondes in the arctic. Bull. Amer. Meteorol. Soc., vol. 85, no. 12, pp. 1855–1861 (2004).

7. Sundar K., Rathinam, S.: Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots. IEEE Trans. Autom. Sci. Eng., vol. 11, no. 1, pp. 287–294, (2014).

8. Murray, C. C., Chu, A. G.: The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transp. Res. C Emerging Technol., vol. 54, pp. 86–109 (2015).

9. Jeong, H.Y., Lee, S., Song, B.D.: Truck-drone hybrid delivery routing: payload- energy dependency and no-fly zones. Int. J. Prod. Econ. 214 (2019). https://doi.org/10.1016/j.ijpe

10. Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52 (2018). https://doi.org/10.1287/trsc

11. Ha, Q., Deville, Y., Pham, Q., Ha, M.: On the min-cost traveling salesman problem with drone. Transp. Res. Part C 86, 597–621 (2018).

12. Bouman, P., Agatz, N., Schmidt, M.: Dynamic programming approaches for the traveling salesman problem with drone. Networks 72 (4), 528–542 (2018).

13. Tu, P., Dat, N., Dung, P.: Traveling salesman problem with multiple drones. In: Proceedings of the Ninth International Symposium on Information and Communication Technology. ACM, pp. 46–53 (2018).

14. Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J.M., Brunese, P.A.: Multiple traveling salesman problem with drones: mathematical model and heuristic approach. Comput. Ind. Eng. 129, 14–30 (2019).

15. Murray, C., Raj, R.: The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones. (2019). https://doi.org/10.2139/ssrn.3338436.

16. Park, S., Zhang, L., Chakraborty, S.: Battery assignment and scheduling for drone delivery businesses. IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED, Taipei, Taiwan, pp. 1–6. (2017).

17. Dorling, K., Heinrichs, J., Messier, G. G., Magierowski, S.: Vehicle routing problems for drone delivery. IEEE Trans. Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70–85, (2017). https://doi.org/10.1109/TSMC.2016.2582745
18. Hill, R. R.: A Monte Carlo study of genetic algorithm initial population generation methods. Proc. 31st Conf. Winter Simulation–A Bridge to the Future, Phoenix, AZ, pp. 543–547. (1999).

19. Razali, N. M., Geraghty, J.: Genetic algorithm performance with different selection strategies in solving TSP. Proc. world Congr. Eng., pp. 1–6 (2010).

20. Al-Kodmany, K.: Skyscrapers in the twenty-first century city: a global snapshot. *Buildings* 8 (12) (2018).