Urban Air Logistics with Unmanned Aerial Vehicles (UAVs): Double-Chromosome Genetic Task Scheduling with Safe Route Planning

Highlights

What are the main findings?

• Developed a combined task scheduling and path planning framework for enabling optimized and safe drone delivery services in an urban environment.
• Utilized a constrained optimization-based framework to allocate both parcel pick-up and delivery tasks and re-charge tasks to a fleet of UAVs in an urban context. The energy efficiency, tasks’ due dates, UAVs’ capabilities, and risks of the UAVs’ flyable paths are taken into account in the combined double-chromosome evolutionary-based task scheduling and path planning methodology.

What are the implications of the main findings?

• The proposed approach combining task allocation and path planning offers both a scalable optimization solution to the NP-hard problem addressed in this work (i.e., the drone delivery problem) and a flexible tool adaptable to other scenarios and task types.
• Addressing the allocation of re-charge tasks along with the allocation of delivery tasks in the same framework represents a comprehensive resolution approach to the drone delivery problem; also, ensuring service persistency and, thanks to the risk-aware UAV route planner integrated to the evolutionary-based task scheduling algorithm, feasibility of deployment in smart city context.

Abstract

In an efficient aerial package delivery scenario carried out by multiple Unmanned Aerial Vehicles (UAVs), a task allocation problem has to be formulated and solved in order to select the most suitable assignment for each delivery task. This paper presents the development methodology of an evolutionary-based optimization framework designed to tackle a specific formulation of a Drone Delivery Problem (DDP) with charging hubs. The proposed evolutionary-based optimization framework is based on a double-chromosome task encoding logic. The goal of the algorithm is to find optimal (and feasible) UAV task assignments such that (i) the tasks’ due dates are met, (ii) an energy consumption model is minimized, (iii) re-charge tasks are allocated to ensure service persistency, (iv) risk-aware flyable paths are included in the paradigm. Hard and soft constraints are defined such that the optimizer can also tackle very demanding instances of the DDP, such as tens of package delivery tasks with random temporal deadlines. Simulation results show how the algorithm’s development methodology influences the capability of the UAVs to be assigned to different tasks with different temporal constraints. Monte Carlo simulations corroborate the results for two different realistic scenarios in the city of Turin, Italy.

1. Introduction

Unmanned Aerial Vehicles (UAVs), commonly referred to as drones, have become increasingly popular in recent years due to their versatility and relatively low cost [1]. The versatility of drones makes them a valid resource for a variety of both military [2] and civilian applications [3,4]. The wide spectrum of civilian applications of drones in industries includes, but is not limited to, agriculture [5], surveillance, mapping, monitoring [6], aerial and subterranean inspection [7,8], and last-mile delivery [9], to state a few. In agriculture, drones can be used for crop management, such as monitoring of crop health and identification of areas that need irrigation or fertilizer. UAVs can be used to monitor crowds at events, provide aerial surveillance of large areas, and even aid in search and rescue operations. In mapping, drones can provide high-resolution aerial imaging that can be used to create accurate 3D models of terrains, buildings, and other structures.

As far as last-mile delivery is concerned, drones have the potential to revolutionize the delivery paradigm [10]. With the rise of e-commerce and the increasing demand for faster and more efficient delivery services, drones have emerged as a promising solution for enabling comprehensive aerial delivery services, decongesting traffic aeras, reducing pollution due to trucks, etc. UAVs offer several advantages over traditional delivery methods, including faster delivery times, reduced costs, and the ability to reach remote or difficult-to-access areas [11]. Currently, drones are being designed and used for a range of delivery applications, including delivery of small packages, medical supplies, and food [12]. Companies such as Amazon, UPS, and Google are heavily investing in so-called “drone technology”, and several programs have been launched in different parts of the world to test the feasibility of drone delivery.

As far as the drone delivery applications in urban environment are concerned, UAVs offer unique benefits to parcel transportation services in smart city contexts [13,14,15]. Those benefits can be summarized as follows:

• Enhancement of efficiency, environmental sustainability, and cost of the delivery services. This is due to the capability of UAVs to avoid obstacles on the ground, fly direct paths, reduce delivery times (particularly useful for medical sample transportation), reduce the need for trucks and couriers, and reduce road traffic in congested urban areas (thus improving air quality).
• Enhancement of data collection services. This is due to the on-board sensors of UAVs, which can be used to collect real-time data such as traffic conditions information and population density distribution. Such collected data can then be gathered and sent to a smart city’s information network, consequently contributing to the development of an adaptive and safe smart city infrastructure.
• Enhancement of the level of automation of logistics services. UAVs can collaborate with other robotic systems and transportation services, predicting delivery routes, exchanging data with automated warehouses, etc.
• Enhancement of the coverage of transportation services. By exploiting “drone technology”, it is easier to reach areas with limited road access or heavily densely populated areas. Also, in case of emergency conditions, UAVs can be used to deliver goods of first necessity such as food, medicine, etc.

On the other hand, there are also technical challenges such as short battery life, limited payload capacity, and susceptivity to turbulent weather conditions that have not been completely addressed yet to make drone delivery a reliable and scalable option. Also, as drone technology advances along with its potential application in the context of smart cities and, more generally, populated environments, concerns about safety [16], security, privacy, and noise pollution arise, threatening the feasibility of deployment of the drone technology itself. As such, international regulatory entities such as the FAA and ENAC are focusing on developing regulatory frameworks that mitigate the risk of malfunctions and mid-air collisions, which pose the main threat of damage to people and property [17]. Five main regulatory aspects are currently being targeted: (i) occupancy of the airspace by UAVs, (ii) definition of operational limits, (iii) administrative procedures leading to UAVs’ flight authorization, (iv) pilot licensing, and (v) authorization regarding data collection. Furthermore, the social acceptance of drone operations in populated environments also plays a crucial role in the implementation of large-scale UAV-based services (such as aerial delivery with UAVs), and is currently being studied mainly by means of surveys and questionnaires [18].

Despite the aforementioned challenges, the potential benefits of drone delivery in urban air mobility contexts are significant. By reducing the need for delivery trucks and other vehicles, drones have the potential to significantly reduce traffic congestion and carbon emissions, making them a more sustainable and environmentally friendly option. As the technology continues to advance and regulation become more supportive, drone delivery is likely to become a more common sight in the skies in the years to come [19]. Thus, optimizing UAV mission management, scheduling operations, and service optimization [20] represent key challenges for the efficient deployment of scalable drone-based delivery services in the upcoming smart cities of the next decades.

Scheduling operations in a fleet of UAVs can be primarily seen as a task assignment problem. Being the task assignment problem for the Drone Delivery Problem (DDP), an NP-hard combinatorial optimization problem, several optimization approaches have been developed in the literature such as genetic algorithms [21], market-based algorithms [22], particle swarm optimization algorithms, and neural network-based algorithms. Refer to [23,24,25,26] for comprehensive reviews of task assignment algorithms and optimization approaches for networks of UAVs. In general, each drone can be assigned to one or multiple tasks, and the goal of the task assignment algorithm is to efficiently allocate tasks to the different drones of the fleet, taking into account task requirements, UAV capabilities, etc.

The task scheduling problem for UAV networks is deeply interconnected to the path planning problem [27]. Especially when considering drone applications in the complex context of urban environments, task allocation and path planning mutually influence each other. For instance, the best allocation may be influenced by the available drone route, and the drone path may depend on the characteristics of the task being assigned. Therefore, the integration of those two components (i.e., task allocation and route planning) is fundamental for the development of safe, efficient, and feasible drone operations in urban environments [28].

The problem addressed in this work is a pick-up and delivery DDP with charging hubs and task due dates. In this paper, we propose a development methodology of a double-chromosome evolutionary-based task planning and optimization framework for a safe and energy efficient aerial package delivery system. The proposed framework aims to optimize the distribution of tasks among a fleet of UAVs with the goal of minimizing the overall energy consumption while ensuring the tasks’ delivery due dates are met. We advance the state-of-the-art by proposing a genetic-based optimization framework that generates both delivery and recharge task schedules for UAVs, with optimal task execution velocity and minimum risk paths that connect the points in the operational area. The risk-aware path planning method adopted in this work is modularly integrated into the task scheduling approach, thereby reducing the computational complexity of the algorithm. The main contributions of this work are (i) the formalization a multi-objective aerial package delivery problem based on multi-rotor UAVs, (ii) the development of an evolutionary-based approach to allocate heterogeneous tasks to a heterogeneous fleet of UAVs, (iii) the integration into the genetic-based algorithm of both an energy-aware task execution velocity optimizer and a risk-aware path planner for feasibility of deployment in urban environments. The proposed framework is evaluated with two real world scenarios in the city of Turin, Italy.

The aim of this work is to cover the literature gap in the field of combined task scheduling and safe path planning by providing a scalable and modular solution to the aforementioned interconnected problems. In particular, the proposed solution addresses the challenges that arise when developing combined task allocation and path planning approaches. Such challenges are related to (i) the high computational complexity of multi-objective optimization problems with many variables and constraints, (ii) the issues of safety and regulatory compliance, and (iii) the adaptability of the method to dynamic conditions such as variations in the map of the operational area and variations in the task set to be allocated.

To the best extent of our knowledge, a comprehensive evolutionary-based task scheduling algorithm combined with a risk-aware path planning approach for solving a complex and multi-objective drone delivery problem like the one formulated in this work is absent in the literature.

This paper is organized as follows. A literature review of state-of-the-art methods addressing the drone delivery problem in terms of task scheduling and route planning is presented in Section 2. Section 3 presents the problem formulation. Section 4 describes the development of the double-chromosome evolutionary-based scheduling framework. The path planning methodology integrated to the task scheduling algorithm is discussed in Section 5. Simulation results are presented in Section 6. Our conclusions are drawn in Section 7.

2. Related Work

A literature review of optimal scheduling (and planning) approaches for the aerial drone delivery problem is presented in the following paragraphs.

An operation management method is proposed in [29], showing that modularity can help in optimizing delivery time and energy consumption in a drone-based delivery system. An adaptive large neighborhood search metaheuristic is proposed in [30] for coordinated truck and drones’ pick-up and delivery schedules. The work in [31] proposes a multi-objective stochastic model for a drone delivery scheduling problem, and a real dataset from the city of Singapore is used to validate the model. The optimization model presented in [32] minimizes the distance traveled by the drone to complete pick-up and delivery schedules, synchronizing with docking charge stations. The effects of battery, charging speed, drone weight, and battery capacity on a drone delivery scheduling model is investigated in [33] for a real scenario in South Korea. A large neighborhood search approach optimizes trajectories, depot locations, and battery allocation in [34] for a UAV-based humanitarian logistics mission. A set of scheduling algorithms based on dispatching rules, randomization, and iterative methods are proposed in [35], showing the capability of minimizing the total time of the supply chain process with UAVs. A novel bi-objective optimization problem for drone pick-up and delivery of medical samples is addressed in [36], and a heuristic algorithm based on NSGA-II is proposed. The work in [37] proposes a Stochastic Event Scheduling (SES) framework to allocate on-demand meal delivery tasks with stochastic due dates to a UAV-based Intelligent Transportation System (ITS). Solutions are optimized with a sub-optimal local search algorithm based on simulated annealing. A combined task scheduling and flight path planning MILP approach is developed in [38] to perform strategic planning of drone deliveries with a Battery Consumption Rate (BCR)-aware feature. The output of the algorithm (based on both a variable preprocessing approach and a primal and dual bound generation method) is the minimum number of UAVs (and their flight paths) needed to execute the task set, ensuring their safe return before consuming their battery life. A sensitivity analysis to assess the impact of wind on drone delivery schedules is conducted in [39], and a UAV scheduling model considering the role of the wind is proposed. A Simulated Annealing-based Two-phase Optimization (SATO) approach is developed in [40] to solve a drone pick-up and delivery problem where the top areas of buildings are exploited as parcel pick-up and delivery locations to be visited by the UAVs. In the first phase, task allocation is performed by means of an Improved Variable Neighborhood Descent (IVND) algorithm. Secondly, a local search algorithm is implemented for the computation of the paths connecting the drones and the locations to be visited. A coupled approach for Multi-Agent Pick-up and Delivery (MAPD) is also proposed in [41], but with task assignment being informed by delivery costs instead of by lower-bound estimates, which usually occurs in the literature. The work in [42] implements an improved Particle Swarm Optimization (PSO) algorithm to solve a combinatorial optimization problem in the fields of logistics and UAVs, i.e., the Vehicle Routing Problems with Time Windows (VRPTW), with multiple constraints. A two-phase stochastic programming model for a cooperative multiple task assignment problem with stochastic UAV velocity and task due date is formulated in [43], and a genetic-based algorithm is implemented to solve the formulated NP-hard problem. Then, starting from the feasible solution, a path coordinator computes the flight paths considering the task requirements. The problem of “dynamic multiple assignments in multi-dimensional space” for UAV swarms in logistics is tackled in [44], allocating tasks and planning 3D paths dynamically. The solution consists of multiple approaches merged together, including Hungarian and cross-entropy Monte Carlo techniques. With the aim of enhancing the delivery range associated with drone operations, an alternative drone delivery framework cooperating with a public transportation network is studied in [45]. The work focuses on computing feasible drone paths (considering the battery life) by means of a label setting algorithm. The fact that the public transportation network is a stochastic time-dependent network is also taken into account in the proposed stochastic model. A market-based approach is developed in [46] to tackle a multi-UAV task assignment problem with multiple constraints. The cost of the bid of each UAV is determined by means of a multi-layer cost computation method, with one layer for each constraint. The work in [47] proposes a combined task scheduling and risk-aware path planning architecture to enable a safe, persistent, and energy-efficient drone pick-up and delivery system. Both parcel delivery tasks and re-charge tasks are allocated using a multi-auctioneer auction-based algorithm, which is highly scalable and capable of assigning also high priority dynamic delivery tasks. The work by [48] develops a MAPD algorithm with task planning, path planning, and deadlock avoidance (based on the “reserving dummy paths” method) capabilities. The MAPD algorithm firstly computes a task sequence for each agent, then plans paths according to these task sequences. A Uniform Distribution K-means (UD-K) algorithm is employed to decompose tasks into multiple task groups for a multi-UAV urban delivery problem in [49]. This is performed to reduce the complexity of the task allocation problem. Secondly, a Bidirectional–Adaptive Potential Field–Rapidly exploring Random Tree star (Bi-APF-RRT*) algorithm computes the distance matrix for the task group, and a Monte Carlo Tree Search (MCTS) algorithm is used to assign tasks with the objective of minimizing the total distance traveled by the UAVs. A three-phase Adaptive Large Neighborhood Search (ALNS) approach is proposed in [50] to solve a multi-trip Drone Routing Problem with Variable Flight Speeds (DRP–VFS). The approach also considers also how payload and velocity influence the energy efficiency of the aerial delivery system. An energy efficient task allocation method is also proposed in [51] by means of a MCTS algorithm. The work in [52] investigates the possibility of forming teams of UAVs in order to allocate parcel delivery tasks and overcome the payload capacity of each UAV.

3. Problem Statement: Drone Pick-Up and Delivery Problem (DDP) with Charging Hubs

The task scheduling problem addressed in this work consists of allocating a set of delivery tasks to a fleet of UAVs. Each delivery task consists of the transportation of a payload mass from a pick-up location to a delivery location within a delivery time window in a populated urban context. The main goal is to allocate all of the delivery tasks while minimizing the total energy required by the fleet of UAVs to complete all tasks. Refer to the “nomenclature” section at the end of the manuscript for the complete list of symbols adopted in this work.

The estimated energy consumption $E_{t_j^i}\left(v_j^i\right)$ related to the execution of the delivery task $t_j$ by UAV $i$ with velocity $v_j^i$ is defined as the solution of an optimization problem, as follows:

$$\min \left(E_{t_j^i}\left(v_j^i\right)={\displaystyle \frac{1}{\eta }}\left(c_d^i\rho A_d^i\left({L_1}_j^i+{L_2}_j^i\right){v_j^i}^2+{\displaystyle \frac{{L_2}_j^i\sqrt{{\left[\left(m^i+{m_p}_j\right)g\right]}^3}}{v_j^i{F}_M^i\sqrt{2\rho A_r^i}}}+{\displaystyle \frac{{L_1}_j^i\sqrt{{\left(m^{i}g\right)}^3}}{v_j^i{F}_M^i\sqrt{2\rho A_r^i}}}\right)\right)$$

(1)

Subject to the following constraints:

$${0\le E}_{t_j^i}\left(v_j^i\right)\le E_{MAX}^i$$

(2)

$$0<\left(v_j^i\right)\le v_{MAX}^i$$

(3)

$$0\le \left({t_t}_j^i\left(v_j^i\right)=T_i^i+{\displaystyle \frac{{L_1}_j^i+{L_2}_j^i}{v_j^i}}\right)\le {T_{DD}}_j$$

(4)

The energy consumption model subject to minimization in Equation (1) takes into account the energy required by a small multi-rotor UAV to resist the drag in forward flight and the weight of the UAV itself, with the assumption of small tilt angles during the flight and negligible wind velocity, as in [53]. The constraint defined in Equation (2) suggests that the energy consumption related to the execution of delivery task $t_j$ by UAV $i$ does not exceed the maximum energy in the battery of UAV $i$. Equation (3) suggests that the optimal task execution velocity $v_j^i$ shall not exceed the maximum speed of UAV $i$. Equation (4) defines the constraint on the delivery time window of task $t_j$, such that the total task execution time ${t_t}_j^i\left(v_j^i\right)$ does not exceed the task’s due date ${T_{DD}}_j$. The optimization variable of the optimization problem defined above is $v_j^i$, while all the other parameters are constants. The parameters are updated according to both the task and the UAV type for which the optimization problem is solved.

Secondly, the sub-problem of scheduling charge tasks is addressed with the aim of minimizing the impact on the delivery process, i.e., the flight time needed by the UAV to visit the nearest charging hub. Recharging tasks are defined by a charge hub location within the operational area, upon reaching which the drone’s battery is swapped with a fully charged one by an operator in negligible time. The recharge task allocation is enabled whenever a UAV does not have sufficient energy in the battery to perform the next assigned task. Since the delivery framework formulated in this work only considers the phase of forward flight of the UAVs, the duration of the drone’s battery swapping phase can be neglected, together with the duration of take-off and landing phases. In the case of recharge tasks, the optimization problem is defined as follows:

$$\min \left(t_{t_j^i}\left(v_j^i\right)\right)$$

(5)

Subject to the following constraints:

$${0\le E}_{t_j^i}\left(v_j^i\right)\le E_{av}^i$$

(6)

$$0<\left(v_j^i\right)\le v_{MAX}^i$$

(7)

Note that the symbols adopted for charge tasks are the same as the ones adopted for delivery tasks, but (since no payload is transported by UAV $i$ visiting charge station $j$) ${L_2}_j^i=0$ and ${m_p}_j=0$ in case of charge tasks. Equation (5) minimizes the flight time ${t_t}_j^i\left(v_j^i\right)$ of UAV $i$ to the charge hub $j$. Equation (6) suggests that the UAV reaches the charge station without exceeding the residual energy in the battery. Again, the optimization variable of the optimization problem defined above is $v_j^i$, while all the other parameters are constants. For the sake of clarity, it is hereby specified that the subscript $j$ refers to task $j$, while the superscript $i$ refers to UAV $i$.

The optimization problem formulated in Equations (1)–(4) ensures that the estimated energy consumption for task execution is minimized, while respecting the task’s due date and the UAV constraints of battery life and maximum speed. The optimization problem formulated in Equations (5)–(7) ensures that the impact of recharge task execution on the delivery process is minimized (minimization of flight time to the charge hub in Equation (5)), while the UAV constraints of battery life and maximum speed are respected. The safety of the risk-aware flyable paths ($L_1$ and $L_2$) is addressed independently from the optimization problem, as discussed in Section 5.

The addressed DDP is defined with some simplifying assumptions such as constant UAV speed throughout task execution, constant flight altitude, no idle time in between tasks, and straight UAV trajectory for both energy and task execution time estimation. Figure 1 shows a simple instance of the problem.

4. Double-Chromosome Evolutionary Task Scheduling Algorithm

A Genetic Algorithm (GA) is a type of optimization algorithm inspired by the processes of natural selection and genetics [54]. It starts with a population of potential solutions to a problem and iteratively improves them by applying a set of genetic operations such as selection, crossover, and mutation. The process begins with the creation of an initial population of potential solutions. Each solution is represented as a string of values, called chromosomes, which can be thought of as the candidate solution’s genes. These chromosomes are evaluated according to some fitness function, which determines how well they solve the problem. The genetic operators then begin to act on the population. The selection operator chooses the fittest individuals from the population and allows them to reproduce by generating offsprings. The crossover operator combines the chromosomes of two individuals to create a new individual, while the mutation operator modifies an individual’s chromosome in a random way to introduce new genetic material [55]. The new population of individuals produced by these operators is then evaluated, and the process is repeated until a satisfactory solution is found or some stopping criterion is met. The reason why GAs are well-suited to solve NP-hard problems is that they are able to search broad portions of the solution space efficiently. NP-hard problems are those that cannot be solved in polynomial time, and traditional optimization techniques such as brute force methods become computationally infeasible as the problem size increases. GAs are able to effectively search large portions of the solution space by exploring multiple solutions simultaneously and avoiding becoming stuck in local optima prematurely. The ability to maintain a diverse population of potential solutions also helps preventing premature convergence to preliminary sub-optimal solutions [56]. Overall, GAs are a powerful and flexible optimization tool that can be applied to a wide range of problems, including those that are NP-hard, such as the DDP addressed in this work.

As the formulated DDP is a complex and multi-objective problem, the main reasons for developing a GA-based approach to solve it can be summarized as follows:

• Capability of incorporating different constraints (battery life, due date constraints, payload capacity) into the optimization process.
• Capability of exploring a broad set of solutions, thereby being able to find solutions to the highly constrained DDP with different objectives.
• Ease of flexibility of the objective function, thereby being easily applicable to different problem formulations (which may occur due to regulative and commercial aspects).
• Ease of adaptability to dynamic changes in the service requirements (both UAVs and tasks’ parameters) since the population of solutions evolves at every iteration.
• High potential of finding innovative solutions which, for a DDP, may be limited to the intuitiveness of traditional greedy approaches.
• Independence from a rigorous mathematical formulation of the problem, which is very challenging in drone delivery scenarios.
• Independence from gradient data (the objective function based on $E_t$ is nonlinear).

Algorithm 1 shows the main body of the proposed double-chromosome genetic algorithm with $r{c}_e=0$. In the double-chromosome encoding logic, the first chromosome $C_I$ represents the task delivery sequence, while the second chromosome $C_{II}$ encodes the cut positions in $C_I$. In $C_I$, each gene represents the index of a delivery task. To ensure the validity of the solution, the genes in chromosome I must be unique, and the total number of genes is equal to $N_T$. The value of any gene in $C_{II}$ must not be smaller than the values of the genes that precede it. Additionally, the number of genes in $C_{II}$ is set to $N_U-1$ to ensure that the task delivery sequence in $C_I$ is partitioned into $N_U$ subsequences.

Algorithm 1. Genetic-based task allocation framework ($r{c}_e=0$)

create random $P$ with $N_P$ individuals

while termination condition is not met do

end

At each iteration of the GA, in order to explore broader regions of the solution space, an opposite population is created based on the principle of opposition-based learning, i.e., the opposite of a weak attribute is a strong attribute. For each integer $z_i$ in $C_I$ of an individual, the opposite is defined as $z_i^{\prime }=a+b-z_i$, with $i\in \left[0,N_T\right], a=0, b=N_T$. As an example, if $C_I=\left(\mathrm{1,7},\mathrm{0,4},\mathrm{5,3},\mathrm{6,2}\right)$, then $C_I^{\prime }=(\mathrm{6,0},\mathrm{7,3},\mathrm{2,4},\mathrm{1,5})$. The crossover operator creates an offspring chromosome from a pair of parent chromosomes. In this case, the Partial Mapped Crossover (PMC) operator is adopted with probability $p_c$. Algorithm 2 shows how $P$ undergoes the PMC operator. Figure 2 show a schematic representation of the operation. Algorithm 3 illustrates the logic behind the mutation operator. Different mutations are applied to each pair of chromosomes. $C_I$ is subject to flip, swap, and slide mutations, while $C_{II}$ undergoes the regenerate mutation. Examples of slide, flip, and swap mutations are reported in Figure 3, Figure 4, and Figure 5, respectively. The regenerate mutation operator randomly regenerates each gene of chromosome $C_{II}$ while satisfying the constraints of $C_{II}$ itself.

Algorithm 2. Crossover in population $P$

for $i=1\to N_P$ do

end

Algorithm 3. Mutation in population $P$

for $\forall$ group of $Z=8$ individuals in $P$ do

end

To ensure that the final solution satisfies the constraints imposed by the problem, each individual in $P$ and $P_{OPP}$ undergoes a feasibility check. While the payload constraint is considered hard, meaning that all solutions must respect it, the delivery time constraint can be either hard or soft depending on the parameter $m_{dw}$. The feasibility check is performed after mutation and crossover operations, which increase the diversity and randomness of individuals in the population. In this way, it is possible to find feasible individuals even when starting from unfeasible ones. Individuals that do not satisfy the constraints are removed from the respective population and do not undergo the subsequent selection process. Algorithm 4 shows how charge tasks are added to an individual. Only delivery tasks are present in $C_I$, and charge tasks are added to create a feasible solution. The assigned charge tasks are not considered in the subsequent rounds of the genetic algorithm and are not subject to crossover and mutation operations. For each UAV, the algorithm runs through each task in the task list one at a time, and after calculating the energy required for the task to be completed, it checks whether there is sufficient energy in the UAV’s battery. If the battery level is sufficient for task completion, the energy required for the task is subtracted from the battery level and the position of the UAV is updated with the final position of the task. If the battery level is not sufficient, a charge task is added before the assigned delivery task, and the position is updated accordingly.

Algorithm 4. Insert charge tasks in individual $I$

Decode $C_I$ and $C_{II}$ of $I$ in the task list of each UAV for $i=1\to N_U$ do

end

The individuals’ evaluation phase is designed to minimize the total energy required by the fleet of UAVs to execute all of the assigned tasks. The fitting function $J$ to be minimized is defined as follows:

$$J=\xi \sum _{i=1}^{N_U}{E}_{TOT}^i=\xi \sum _{i=1}^{N_U}\sum _{j=1}^{N_T}{E}_{t_j^i}$$

(8)

$\xi =1$ in case of $m_{dw}=1$, while $\xi =p_{ot}^{-1}$ if $m_{dw}=0$. With the parameter $\xi$ included in the fitness function, it is possible to prioritize the energy consumption with respect to the compliance to all task due dates, i.e., the algorithm can tackle a very demanding task set in terms of delivery due dates.

Then, an offspring population is created by merging individuals from both $P$ and $P_{OPP}$. Specifically, half of the individuals are randomly selected from $P$, and the remaining half from $P_{OPP}$. $n_{best}$ individuals with the highest fitness scores from both populations are automatically included in the new population $P\prime$. The remaining individuals in $P\prime$ are selected according to a roulette wheel technique: each individual is assigned to a selection probability proportional to its fitness value. The termination condition is defined as either $n_i=n_{max}$ or $∆J<\epsilon$, in the last $n_{conv}$ iterations.

A simple instance of the DDP formulated in this work is used to show how the proposed scheduling approach works. The simple scenario consists of five pick-up and delivery tasks to be allocated to a fleet of two UAVs. Two charge hubs are located within the operational area. The due date of each task is randomly assigned between 0 and 3 h.

Figure 6a shows the UAV task assignments related to the final solution of Algorithm 1 ($m_{dw}=0$) for the simple scenario. The execution of a delivery task is represented by means of a continuous line connecting the pick-up location to the delivery location, while dotted lines represent the movement of the UAVs from their initial locations to either the delivery tasks’ pick-up locations or the recharge hubs’ locations. Figure 6b shows the evolution of the fitness function $J$ at each iteration of the double-chromosome genetic task scheduling algorithm.

Algorithm 5 shows the main body of the proposed GA with $r{c}_e=1$. Four different versions are implemented in total: Algorithm 1 with $m_{dw}=1$ or $m_{dw}=0$, and Algorithm 5 with $m_{dw}=1$ or $m_{dw}=0$.

Algorithm 5. Genetic-based task allocation framework ($r{c}_e=1$)

create random $P$ with $N_P$ individuals

while termination condition is not met do

end insert charge task in final $P$

5. Risk-Aware Path Planning Methodology

In the proposed evolutionary-based task allocation framework, the paths connecting the UAVs’ position to the tasks’ position are computed by a risk-aware path planner with the aim of demonstrating the potential capability of deployment in urban context. To achieve this, the risk-aware path planning method proposed in [57] is adopted. This method involves a two-step procedure with the generation of a risk map followed by a risk-aware path planning algorithm that searches for the minimum risk path while minimizing the overall risk and the flight time. As described in [58], the risk map is a two-dimensional location-based map, where each element represents a specific location and is associated with a risk value. The risk value is computed using a probabilistic ground risk assessment approach that estimates the expected frequency of fatalities after a ground impact accident. The risk map depends on the UAV type (mass, dimensions, and maximum flight speed, and other parameters). Thus, a risk map must be computed for each UAV type, including the mass of the payload. After generating the risk map, the risk-aware path planning approach utilizes the RRT* algorithm [59] to compute the minimum risk path. RRT* explores the search space, constructing an asymptotically optimal tree, and the near-optimal solution is the branch of the tree that connects the start and goal locations. The method is used to minimize the overall risk and the flight time. The risk is expressed in fatalities per hour, and is proportional to the flight time. Before passing the safe paths’ length as constant parameters to the task scheduling framework, the average risk of the minimum risk paths is compared to an Equivalent Level of Safety (ELOS) [60], to determine if the resulting paths are sufficiently safe or not.

As demonstrated in [57,58], the proposed risk-aware path planning methodology is able to search for the minimum risk path in the risk map and is a promising tool for risk-informed decision making. However, the resulting risk and the safe path computed depend on the operational area and UAV type.

The risk computed by the risk map is proportional to the number of people exposed to crash and the estimated kinetic energy at impact. Consequently, the risk is higher in areas with a high population density and in open spaces, i.e., areas where people are completely exposed to a possible crash of the UAV. This trend can be observed in the risk maps of Figure 6, in which the risk is higher in the Turin city center and, in particular, in correspondence with the main squares and large busy roads.

On the other hand, the risk depends on the involved kinetic energy at impact and, intuitively, is proportional with the UAV mass and velocity.

For this reason, the adoption of a heterogeneous fleet of drones allows for the selection of the UAV best suited to the characteristics of the area being flown over. Strictly speaking, lighter UAVs are suitable for flying over high-risk areas (city centers and busy roads), while heavier UAVs are more suitable for flying over suburban areas or, in any case, where there is a lower risk.

As far as the scalability to larger urban areas is concerned, being the risk map generated by computing the risk for each cell (i.e., location) in the map, the computational complexity increases proportionally to the number of cells and, therefore, with the dimension of the map. However, the resolution of the risk map can be adequately modified to manage large urban areas without making the method intractable, as demonstrated in [10].

A larger urban environment also implies an increase in the computational complexity of the risk-aware path planning algorithm, which operates on the map. As discussed in [59], the computational complexity of RRT* can be approximated to $O\left(z\log z\right)$, with z being the number of nodes sampled within the risk map. Consequently, the path planning algorithm requires more nodes to obtain an optimal path, but the algorithm is still able to provide solutions within a reasonable computation time.

6. Simulation Results

The algorithms are implemented in Python 3 and tested with two complex scenarios, representing real-world situations with tens of tasks and a few UAVs. The optimization problems formulated for estimating the optimal tasks’ execution velocities are solved using the Phyton’s constrained optimization tool (scipy.optimize). The characteristics of the fleet are reported in

Table 1. Characteristics of the fleet of UAVs.

UAV Type	m [kg]	${\mathit{A}}_{\mathit{r}} \left[{\mathbf{m}}^2\right]$	${\mathit{A}}_{\mathit{d}} \left[{\mathbf{m}}^2\right]$	${\mathit{v}}_{\mathit{m}\mathit{a}\mathit{x}} [\mathbf{m}/\mathbf{s}]$	${\mathit{E}}_{\mathit{M}\mathit{A}\mathit{X}} \left[\mathbf{M}\mathbf{J}\right]$
A	$1$	$0.2$	$0.4$	$16$	$0.68$
B	$2$	$0.28$	$0.6$	$19$	$0.9$
C	$3$	$0.36$	$0.8$	$20$	$1.17$
D	$4$	$0.44$	$1$	$22$	$1.43$

. For every UAV, $FM$ is set to 0.9, $c_d$ is set to 0.3, $\eta$ is set to $0.9$, and the air density is set to $1.23 \mathrm{k}\mathrm{g}/{\mathrm{m}}^3$. The maximum payload capacity of each UAV is assumed to be equal to its mass.

The tasks set is selected from a set of $N_T=40$ points in the operational environment: a portion of the city of Turin, as in Figure 1. The extremities of the operational area in terms of latitude and longitude are defined as $[45.0379°,45.0743°]$ and $[7.6146°,7.6894°]$, respectively. The task set is homogenously divided in $5$ payload weight classes: $0.5$, $1$, $2$, $3$, and $4$ kg. Additionally, $N_C=4$ charging hubs are defined in the operational environment. $N_U$ is set to $8$, with $2$ UAVs per type. The genetic algorithm is configured such that both $p_m$ and $p_c$ are set to $0.3$, $N_P=30$, the number of elite individuals selected for the next generation is set to $5$ ($n_{best}=5$), the convergence threshold $n_{conv}$ is set to $8$, the energy tolerance between the last solutions ($\epsilon$) is set to $300 J$, and $n_{max}$ is set to $20$.

The path planner is launched prior to the task allocation algorithm to reduce the computational burden. The path planner computes the distances of the safe paths between the points and saves them in a matrix (triangular with zero diagonal) that is accessed by the scheduling algorithm.

In order to both justify the use of the risk-aware path planner and demonstrate its effectiveness; Figure 7 shows some notable examples of risk maps and minimum risk paths. For the aforementioned examples, we have selected the area in Figure 1 because it includes heterogeneous areas: the city center with high population density; a suburban hilly area with low population density; and the presence of a river that represents the natural corridor for a low-risk route.

The risk map depends on the type of drone used and the payload carried, since the kinetic energy on impact depends on the mass. UAV A provides a lower level of risk in the map compared to UAV C, and, in addition, the payload of 2 kg further increases the risk. Changes in the risk maps lead to different routes computed using the risk-aware path planning approach that searches for an optimal path minimizing the risk and flight time.

The maximum and minimum risk in the risk maps, as well as the average risk and the total length of each path in Figure 7 are reported in

Table 2. Risk values and other parameters of risk maps and paths in Figure 6.

UAV Type	Risk Map		Min. Risk Path		Min. Distance Path
	Max Risk [h−1]	Min Risk [h−1]	Av. Risk [h−1]	Distance [m]	Av. Risk [h−1]	Distance [m]
UAV A	$3.72·{10}^{-6}$	$2.17·{10}^{-8}$	$1.42·{10}^{-7}$	$3654.8$	$6.44·{10}^{-7}$	$2541.6$
UAV C	$2.99·{10}^{-5}$	$1.72·{10}^{-7}$	$1.07·{10}^{-6}$	$3919.9$	$3.37·{10}^{-6}$	$2542.3$
UAV C with 2.0 kg of Payload	$4.21·{10}^{-5}$	$2.40·{10}^{-7}$	$1.43·{10}^{-6}$	$4041.88$	$5.17·{10}^{-6}$	$2539.2$

. Observing the results in Table 2, the minimum risk paths are obviously longer than the minimum distance paths, but they involve a decidedly lower risk.

Two scenarios are considered: scenario A involves random assignment (between $0$ and $3$ h) of the delivery window to each task, and scenario B assumes a uniform delivery window of 5 h for all tasks. Each scenario is tested using all four versions of the algorithm, i.e., with all the combinations of the binary parameters $m_{dw}$ and $r_{ce}$. The results are reported in terms of mean value $\vartheta$ and standard deviation $\mu$ for 20 Monte Carlo simulations. The results in terms of well-defined solution quality parameters ($E_{TOT}$, $p_{ot}$, $n_{char}$, $n_i$, $t_{tot}$) are presented in

Table 3. Results of Monte Carlo simulations for scenario A.

${\mathit{m}}_{\mathit{d}\mathit{w}}$$/{\mathit{r}}_{\mathit{c}\mathit{e}}$	ETOT [MJ] $\mathit{\mu }\pm \mathit{\vartheta }$	pot $\mathit{\mu }\pm \mathit{\vartheta }$	nchar $\mathit{\mu }\pm \mathit{\vartheta }$	ni $\mathit{\mu }\pm \mathit{\vartheta }$	ttot [s] $\mathit{\mu }\pm \mathit{\vartheta }$
$1/0$	0	0	0	0	0
$0/0$	$15.79\pm 0.52$	$0.857\pm 0.030$	$4\pm 0$	$8.9\pm 4$	$2690\pm 1549$
$1/1$	$0$	$0$	$0$	$0$	$0$
$0/1$	$16.09\pm 0.60$	$0.879\pm 0.017$	$4\pm 0$	$9\pm 5.2$	$527\pm 340$

and

Table 4. Results of Monte Carlo simulations for scenario B.

${\mathit{m}}_{\mathit{d}\mathit{w}}$$/{\mathit{r}}_{\mathit{c}\mathit{e}}$	ETOT [MJ] $\mathit{\mu }\pm \mathit{\vartheta }$	pot $\mathit{\mu }\pm \mathit{\vartheta }$	nchar $\mathit{\mu }\pm \mathit{\vartheta }$	ni $\mathit{\mu }\pm \mathit{\vartheta }$	ttot [s] $\mathit{\mu }\pm \mathit{\vartheta }$
$1/0$	$15.06\pm 0.6$	$1\pm 0$	$4\pm 0$	$7.8\pm 3.4$	$2428\pm 1375$
$0/0$	$14.79\pm 0.46$	$1\pm 0$	$4\pm 0$	$8.2\pm 3.2$	$2354\pm 1503$
$1/1$	$15.50\pm 0.62$	$1\pm 0$	$4\pm 0$	$7.4\pm 3.2$	$347\pm 341$
$0/1$	$15.70\pm 0.81$	$1\pm 0$	$4\pm 0$	$8.8\pm 3.6$	$373\pm 199$

.

It should be noted that the versions of genetic algorithm with $m_{dw}=1$ aim to assign all tasks to the entire fleet, and if a solution satisfying delivery time and payload constraints cannot be found, the algorithms will return no output. This is why the versions with $m_{dw}=1$ do not produce any result for scenario A, which represents a scenario with “hard” constraints. However, versions with $m_{dw}=0$ achieve a delivery success rate of $86\%$ and $88\%$, denoting that the total energy consumption can be minimized by delivering most of the parcels within the available delivery time window.

Interestingly, the versions with $r_{ce}=0$, which add charging tasks at each iteration of the GA rather than just at the end, provides the minimum energy solution. However, the energy savings are only about $2.5\%$, which may not be significant compared to the increase of $600\%$ in execution time, with respect to the versions with $r_{ce}=1$. Analogous considerations can be drawn from the results related to scenario B, where, because of larger and uniform delivery time window for all tasks, we have a solution with all versions of the GA.

The results obtained with both the implementation of the aforementioned simulation campaigns and the analysis of the solution quality parameters (for all variants of the proposed GA-based framework) enabled the following conclusions:

• The proposed architecture successfully tackled the formulated DDP with real-world instances of the problem itself. The Monte Carlo simulations corroborated the validity of the approach.
• The algorithm was able to tackle scenarios with “hard” constraints, i.e., tens of delivery tasks with random deadlines. This is due to the conceptualization of the $m_{dw}$ binary variable, which enabled the possibility of considering late schedules as feasible solutions.
• The integration of the risk-aware path planning approach into the GA-based solution did not increase the computational complexity of the proposed GA. This is because the UAV-task route planning approach is a pre-processing approach with respect to the scheduling algorithm (all of the paths for each possible UAV-task assignment are computed twice: with and without payload). Therefore, the approach is scalable with respect to the number of UAVs, number of tasks, and dimension of the operational area.
• The decoupled scheduling of delivery tasks and recharge tasks does not decrease significantly the level of optimality of the final schedules (about $2\%$), but decreases about $600\%$ of the algorithm’s execution time. This means that adding a greedy strategy when solving a complex combinatorial optimization problem, such as the DDP of this work, within the proposed genetic framework can be preferred over the mere development of a standard genetic approach.

7. Conclusions

This paper offers a thorough examination of the development of a double-chromosome evolutionary-based optimization framework for planning efficient and safe drone deliveries. The addressed NP-hard problem consists of scheduling delivery tasks with time deadline constraints to a fleet of UAVs in urban environments. Secondly, the problem of scheduling recharge tasks is also addressed to ensure feasibility and persistency of service. The algorithm can both tackle complex scenarios with tens of delivery tasks with random temporal deadlines and minimize the energy consumption of the aerial fleet. A risk-aware path planner is included in the framework, ensuring the evaluation of safe UAV paths. The proposed approach combines task allocation and, as a pre-processing phase, path planning, offering a scalable solution to the NP-hard DDP addressed in this work. The proposed framework is demonstrated to be a flexible tool adaptable to other urban air mobility scenarios, task types, and diverse urban operational areas. The complete task planning methodology based on the genetic algorithm can enable safe, persistent, and energy efficient drone delivery services; thereby presenting itself as a valid candidate software tool for enhancing the sustainability and efficiency of UAV-based intelligent transportation systems in the smart cities of the future. The simulation results based on Monte Carlo simulations, which refer to real world instances of the DDP in the city of Turin, Italy, corroborate the validity of the proposed optimization framework.

The comparison of the performance of the proposed framework with other optimization approaches will be addressed in future works. Also, a MILP model of the addressed problem will be developed and solved using a commercial optimization software such as CPLEX.