Next Article in Journal
Distance-Based Formation Control for Fixed-Wing UAVs with Input Constraints: A Low Gain Method
Next Article in Special Issue
Urban Air Mobility: Systematic Review of Scientific Publications and Regulations for Vertiport Design and Operations
Previous Article in Journal
High-Temporal-Resolution Forest Growth Monitoring Based on Segmented 3D Canopy Surface from UAV Aerial Photogrammetry
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Systemic Performance Analysis on Zoning for Unmanned Aerial Vehicle-Based Service Delivery

Operations Research Group, Department of Materials and Production, Aalborg University, 9220 Aalborg, Denmark
*
Author to whom correspondence should be addressed.
These authors contributed equally to this work.
Submission received: 9 June 2022 / Revised: 20 June 2022 / Accepted: 23 June 2022 / Published: 26 June 2022
(This article belongs to the Special Issue Urban Air Mobility (UAM))

Abstract

:
A zoning approach that divides an area of interest into multiple sub-areas can be a systemic and strategic solution to safely deploy a fleet of unmanned aerial vehicles (UAVs) for package delivery services. Following the zoning approach, a UAV can be assigned to one of the sub-areas, taking sole ownership and responsibility of the sub-area. As a result, the need for collision avoidance between units and the complexity of relevant operational activities can be minimized, ensuring both safe and reliable execution of the tasks. Given that the zoning approach involves the demand-server allocation decision, the service quality to customers can also be improved by performing the zoning properly. To illuminate the benefits of the zoning approach to UAV operations from a systemic perspective, this study applies clustering techniques to derive zoning solutions under different scenarios and examines the performance of the solutions using a simulation model. The simulation results demonstrate that the zoning approach can improve the safety of UAV operations, as well as the quality of service to demands.

1. A Zoning Approach: A Systemic Solution for Successful Airspace Control

Unmanned aerial vehicles (UAVs), or drones, are a game changer in many business and public sectors because of their ability to exploit aerial dimensions and inexpensive operating cost. However, the applications of UAVs are often made with a single or a few UAVs in a relatively safe operation area. One of the reasons for such limited UAV applications is the difficulty in air traffic control and collision avoidance for UAVs [1] for large-scale deployments. Although there have been dramatic advances in technologies for collision avoidance (e.g., artificial intelligence for path finding [2]) and UAV flight system automation, the technologies are not at the desired level to resolve safety issues completely.
This difficulty becomes more significant when multiple UAVs are deployed in a relatively small area at the same time in a dynamic environment. When no cyclical stability on UAV tasks can be identified, this difficulty becomes even worse [3]. This situation can be found in UAV application scenarios with a delivery function, such as UAV-based logistics [4,5], humanitarian/emergency aid operations [6,7], or in cooperation with other unmanned systems [8,9]. These applications are where the demands for services are expected to exceed the supply levels that can be fulfilled with traditional means of transportation, and the task can be performed better with exploitation of the aerial dimension. Therefore, a large-scale UAV fleet deployment is desired to handle the increasing service demands and to maximize the service quality.
A key solution to realize large-scale UAV operations is an unmanned aircraft traffic management (UTM) system, which manages airspace for multiple UAV operations through real-time control. Following the increasing volume of UAV operations and the need for UTM systems, federal regulatory agencies such as the European Aviation Safety Agency (EASA) and the Federal Aviation Administration (FAA) in the United States have conducted several projects and discussed the concepts of UTM and regulations of UAVs [10,11].
While airspace for UAVs is increasingly regulated, the feasibility and performance of UTM is still far behind the desired level, especially considering the envisioned future air traffic densities. Unlike the well-established and -functioning air traffic management (ATM) systems for manned aircraft, the following aspects of UAVs challenge the development of UTM [12]:
  • Different types of UAVs with different performances;
  • Limited capability to carry heavy or power-intensive equipment;
  • Limited capability to automatically detect and avoid collisions;
  • Increasing needs for UAV operations beyond visual line of sight (BVLOS) for greater economic values;
  • High density of operations, likely flying very close to other units;
  • High degree of vulnerability to operational environments (e.g., wind).
These key differences between manned aircraft and UAVs underline the complexity of the development and implementation of a UTM system. UTM implementation involves novel challenges, including decentralization of governing authority over large-scale UAV operations and interactions with pilots to share crucial flight and safety data [13]. When narrowing down the UTM for the safety aspects of UAVs, safety separation standards, collision risk prediction, and collision avoidance can be listed as the critical research topics, and there needs to be significant advances for full- and large-scale UAV operations [14].
Considering the complexity of the involved design and decision-making problems in the UTM, it is clear that a centralized air traffic control (ATC) with a full synchronization of large-scale UAV operations is extremely difficult to achieve. In the context of ATM, the ATC-related decision-making authority is distributed among flight crews, the air traffic service providers, and aeronautical operational control organizations in order to reduce reliance on the centralized ATC [15]. In the context of UTM, however, it is difficult to give UAVs the freedom for their path and speed selection in real time, because full automation of path finding and conflict resolution for large-scale UAV operations in a decentralized manner is highly complex [14,16,17].
As a systemic solution to the difficulties of UTM implementation, a zoning approach, where an operational area for UAVs is decomposed into a set of sub-areas and a maximum of one UAV can be deployed within a sub-area at a given time, can be considered [18]. By this approach, the flight paths of UAVs in different zones do not overlap, and it is likely that UAVs remain well clear with or without minimum control efforts. The flight planning and control problems involved in a UTM can also be made simple, as the interaction level between UAVs are minimized by the zoning approach.
As such, the workload for airspace control and collision avoidance can be dramatically reduced by the zoning approach. Importantly, this reduced workload can be further distributed to the sub-UTMs for each zone in favor of the zoning approach. Given that most of UAV control systems are still operated by humans, this zoning approach also brings advantages to UAV service providers, that is, to reduce the manpower for UAV deployment and corresponding operating costs. The expected benefits of the zoning approach are summarized as follows:
  • Reduced burden to control/monitor UAVs;
  • Reduced risk to safety;
  • Minimum communication between UAVs;
  • Increased chance of UAV flight automation;
  • Scalability for a large-scale UAV deployment;
  • Reduced complexity of relevant planning and control problems in a UTM.
On the other hand, one can question the negative impacts of the zoning approach on the service-to-customers level, as the means to serve demands is restricted by the approach. Indeed, the set of demands or the area a UAV can cover is limited by a zoning solution in terms of volume, size, and location of the demands. Therefore, considering the zoning approach as a demand-server allocation problem, it is important to derive a zoning solution so that the resulting service level to customers is kept at an acceptable level, while fully exploiting the advantages of the zoning approach.
The aim of this study is to demonstrate the advantages of the zoning approach from the UAV safety and service quality perspectives. Specifically, we answer the following questions:
  • How much separation between UAVs is expected to be achieved by the zoning approach?
  • Will the zoning approach result in service quality degradation?
  • What would be the determining factors for the zoning approach performance?
To answer these questions, we analyze the performance of the zoning approach from a systemic perspective. We first generate package-delivery-like scenarios, where multiple demand nodes in an area are served by multiple UAVs. We group the demand nodes using clustering techniques and derive a zoning solution accordingly. The performance of the proposed zoning approach is examined under multiple demand configurations using a simulation model, compared to other benchmark service strategies.

2. Related Work: Zoning in Literature

UAV application areas are numerous and include those domains where automation, low operation costs, and aerial dimension exploitation can bring values. Otto et al. [19] present a comprehensive review on UAV applications, classifying the UAV-involved tasks in the applications and relevant planning problems. Mukhamediev et al. [20] also present detailed UAV use cases in various industry applications, highlighting relevant data management and processing tasks.
The UAV applications where the concept of zoning is relevant can be further classified into two classes: area coverage and package delivery. The area coverage class addresses tasks for searching and monitoring an area, whereas the package delivery class addresses transportation-related activities.
By the nature of the zoning approach, one can easily find its link to the area coverage class, where efficient use of units by properly assigning responsible areas to the units is critical to achieve a service/mission goal (e.g., to minimize the time it takes to search an area). Fu et al. [21] propose a local Voronoi decomposition algorithm for exploration task allocation to multi-agents. In this approach, Voronoi regions of each agent are calculated based on the agents’ positions, and the agents move only within their regions to avoid overlapping tasks. Miao et al. [22] apply a map decomposition approach to assign sub-maps to cleaning robots so that large-scale cleaning areas are effectively distributed and assigned to the robots. Xiao et al. [23] apply area segmentation for UAV coverage planning in a grid map. Once a take-off location is determined, an area of interest is specified as a set of grids and further divided into sub-areas so that the energy required to cover the sub-areas are balanced and collisions between UAVs can be avoided. For three-dimensional coverage path planning, where different coverage paths depending on altitudes of a region of interest are generated [24], multiple UAVs can be assigned to different altitudes for coverage operations.
The zoning approach is also found in the package delivery application class, the focus of the zoning approach in this study. UAV-based package delivery is a UAV application with increasing demands and demonstrated profits. To realize this service concept with minimum barriers to its implementation, various practical issues, such as preserving privacy, have been addressed [25].
The main focus of the zoning approach in this class is collision avoidance and ease of UAV traffic management, the critical challenges for package delivery by UAVs [26]. Amazon, who first introduced the concept of package delivery by UAVs, proposes an airspace model where civil airspace is segregated by altitudes based on vehicle capability [27]. In this model, a low-speed localized traffic area is used for the UAVs without sophisticated sense-and-avoid technology, whereas a high-speed transit area is used for well-equipped vehicles. The model also includes a no fly zone to buffer the UAV operations from current aviation operations. Feng and Yuan [28] apply space zoning to a low-altitude airspace that divides the space into upper, buffer, safe, and bottom zones according to space height restrictions in order to construct flight corridors for UAVs. Sung and Nielsen [18] propose a zoning approach that divides a service area with a single UAV station into zones. They allow at most a single UAV to fly within a zone and investigate the expected service level with these zoning practice using a simulation.
Note that the clustering approaches applied to UAV routing problems for package delivery services can also be seen as a special case of the zoning approach for tactical decision-making. In particular, clustering has been actively applied to truck-assisted UAV package delivery services, where a truck visits multiple spots following a path to support UAVs’ operations (e.g., recharging and (un)loading payloads). Under this service delivery scheme, delivery points are grouped into a set of clusters, and a route for a truck to visit the clusters and routes for UAVs within the clusters are derived to maximize the service delivery performance [29,30,31].
As reviewed, the concept of zoning has been addressed from different perspectives in the literature. In general, the zoning approach is designed to optimize the UAV performance for a single service instance (tactical/operational) under the area coverage class, whereas the zoning approach is applied to design a UAV traffic management system for multiple service instances (strategic) under the package delivery class. The zoning approach for the package delivery class is further separated by the restriction level on a zone. Sung and Nielsen [18] apply the most restricted practice, which allows only a single UAV to fly within a zone at a given time, whereas the other studies separate airspace by altitudes and allow multiple UAV operations in a zone.
Our study is aligned with the work of Sung and Nielsen [18]. It is difficult to assume a full connectivity between UAVs during their operations and 100% reliable UAV control logic mainly due to the dynamics in the airspace and the absence of a decent UTM. Considering this fact, operating UAVs with zoning, as proposed by Sung and Nielsen [18], seems more appropriate for safety and service reliability reasons and can increase the feasibility of large-scale UAV deployment.
Based on the review, the contributions of our study can be noted as follows. We first describe a systemic and strategic solution for application of UAVs to package delivery scenarios, which allows UAV deployment at a large scale and reduces reliance on dramatic advances in UAV navigation and control technology. Next, in contrast to the work of Sung and Nielsen [18], we apply clustering techniques for zoning to address multiple UAV stations in a service area, which can naturally be seen in a large-scale service scenario. Last, we test the performance of the zoning approach under different demand distribution configurations to clearly illuminate the expected benefits of the proposed zoning approach.

3. The Zoning Problem and the Considered Solution Approach

3.1. Problem Description

Assume that multiple demand nodes are distributed in a two-dimensional service area. Demand node x has demand rate λ x and is independent from the other demand nodes in the area. K number of UAVs are available for operation, and a UAV will serve a single demand (a demand instance at a demand node) per trip.
Given the setting, we seek a set of zones Z and base locations μ such that (1) all the demand nodes are divided into K number of zones Z = { Z 1 , Z K } , (2) a flight path between the base of a zone and a demand node within the zone is guaranteed, and (3) the total service level for the demand nodes by the zoning solution is maximized. The zoning problem of this study can be formally described by
P z o n i n g = arg max Z , μ k = 1 K x Z k L ( x | μ k , Z ) ,
where L ( x | μ k , Z ) is the service level for demand node x given a base location μ k and a set of zones Z .
From the safety perspective, the most relevant measure for the service level would be the distance between operating UAVs in different zones. Considering this idea, a zoning solution that maximizes the separation between demand nodes in different zones would be desired. This concept is well-aligned with the k-means clustering algorithm, which partitions observations into k clusters such that observations are assigned to the clusters with the nearest mean. Based on this, the original zoning problem can be rewritten as
P z o n i n g * = arg min Z , μ k = 1 K x Z k λ x · | | x μ k | | 2 ,
which is intended to minimize the weighted within-cluster variances (which is the same as maximizing between-cluster variances). It should be clear that this formulation is one of the options to approximate the original zoning problem (Equation (1)); thus, a different formulation can be designed based on the use case’s specific constraints, for example, the minimum distance between demands and the center of a zone or no-fly zone.

3.2. Solution Approaches: Weighted k-Means Algorithm

The target zoning problem P z o n i n g * is solved by a weighted K-means algorithm (WKMA), based on the Hartigan algorithm for k-means clustering [32]. Instead of using the mean and squared distance when updating centroids, we use the weighted mean and squared weighted distance in order to account for the arrival rate. The WKMA implementation is described in Algorithm 1. The computational complexity of the algorithm is γ · O ( K · D ) , where γ is the number of iterations performed by the algorithm until the clustering solution is converged, and D is the number of demand nodes.
Algorithm 1: WKMA
  • Require: demand set, the number of centroids (k)
1:
Randomly assign all demand nodes to a centroid
2:
Calculate centroids as weighted mean of their assigned nodes
3:
whileNot convergeddo
4:
    for demand node d in demand set do
5:
        for centriod c in centroid set do
6:
            Assign demand node d to centroid c
7:
            Compute the sum of squared weighted distances from each node to its centroid
8:
        end for
9:
        Assign d to the centroid which resulted in the smallest sum
10:
        Recalculate centroids as weighted mean over all nodes assigned
11:
    end for
12:
end while
13:
return demand allocation to centroids

3.3. Benchmark UAV Deployment Strategies

As a benchmark solution to the zoning approach, a strategy termed closest, which assigns the closest available UAV to a demand without restrictions in its operation area, can be considered. Note that from our initial experiments, the closest strategy showed poor performance, because distant demands are often assigned to UAVs, hampering the efficient use of UAVs.
To avoid such a distant demand allocation to a UAV, a relaxed version of the closest strategy, termed closest with thresholds, is introduced. Given base locations, we first set a maximum UAV flight range such that all demand nodes can be covered by at least one UAV. For each demand node, any UAVs placed within the maximum flight range are then considered as a candidate server for the demand. Illustrations of the service areas derived by the three different UAV deployment strategies—the zoning approach, the closest, and the closest with thresholds—are given in Figure 1. In the figure, the base and demand node are represented as a red box and a black circle, respectively.

4. Experimental Results

Following the aim of this study (i.e., to demonstrate the performance of the zoning approach), we simulate UAV trajectories for package delivery scenarios and measure how close to each other UAVs are supposed to fly based on the trajectories. We also evaluate the service quality level for customers based on the simulated trajectories to evaluate the service quality degradation by zoning approach.

4.1. Experimental Setting

We generate four problem classes, varying the settings of the following two design factors: a geographical distribution of demands and a representative package delivery scenario.
For the geographical distribution of demands, we first create demand set U, where 100 demand nodes are uniformly distributed over a square-shaped 2D area. To see the impact of densely located demand nodes on the performance of the zoning approach, we also create demand set C, where demands are primarily located in the center of a service area. This demand set is created by sampling 100 demand nodes from the york dataset available from the r-package maxcovr. Figure 2 shows the two different demand node distributions.
Next, we apply two different service modes to test the zoning approach under different service scenarios. For scenario NQ (no queue), we assume a situation where a service request, which cannot be served immediately by a responsible UAV, will leave the system without receiving service. This scenario represents an emergency situation, where a timely response to a demand is critical (e.g., visual surveillance of a traffic accident). For scenario FCFS, we assume a situation where demands wait until they receive service by UAVs. In this scenario, demands in a queue are handled by the first come first serve (FCFS) policy. This scenario is implemented to represent a commercial package delivery scenario.
Following the setting, we generate the four different problem classes ( { U , C } × { NQ , FCFS } ) and test the performance of the zoning approach in a simulation environment. Note that the objective function of the zoning problem, that is, to minimize the within-zone variances, is a proxy for the actual UAV safety level. Therefore, a simulation model is implemented to investigate the performance of the proposed zoning approach close to its actual performance. In principle, the zoning approach can be applied to a UAV-based service system with any type of UAV. Since we examine the systemic performance of the zoning approach, the detailed dynamics of UAVs (e.g., the minimum turning radius of a unit, energy consumption as a function of weather conditions, and collision avoidance logic during operation) are simplified in the simulation. The simulation model generates demands following the demand rates of demand nodes and assigns available UAVs by the applied UAV deployment strategy, updating the operational status (busy/idle) of the UAVs.
For each problem class, we replicate a simulation run 20 times. The length of the simulation is four hours, and the status of UAVs and demands are updated every second in a simulation run. In the simulation, the demand rate of a demand node (the number of demand requests per minute) is drawn from a uniform distribution with the bounds [ 0.4 , 0.6 ] . The number of UAVs is set by ten to provide a sufficient service capacity for the demands.
The output of a simulation run is the UAV flight trajectories for all time steps (every second), including the positions of UAVs and their status, and the records regarding how demands are served. Based on the output, the separation level between UAVs is analyzed to see how much the safety can be improved by the zoning approach, which is the main topic of this study (Section 4.2). The service quality with regard to the demands is also analyzed to evaluate the performance of the zoning approach from the customers’ perspective (Section 4.3).

4.2. UAV Safety Improvement by the Zoning Approach

Given the UAV flight trajectories obtained from simulation runs, we compute the distances between two operating UAVs at each time stamp to measure the proximity between UAVs. Given that a key performance measurement from the safety perspective would be the separation level between UAV flights, we compute the 5th percentile of the proximity between UAVs (i.e., the distance between two flying UAVs) to identify the minimum distance gap guaranteed for the majority of the UAV flights. Figure 3 shows the distribution of the 5th percentile proximity values for 20 simulation runs under the four different problem classes and the three different UAV deployment strategies (zoning vs. closest vs. closest with thresholds).
From the figure, it is observed that for all the problem classes, the zoning approach shows greater distance gaps than the other considered strategies. While the distance gap increases when the demand distribution C is applied (which seems inevitable due to the density of the demand nodes in the dataset), the zoning approach can still provide greater distance gaps between UAVs than the other strategies. Given that collision avoidance action is taken when a UAV detects an object within a certain range, a greater distance between UAVs clearly indicates that UAVs are likely to be cleared with less efforts for collision avoidance from both UAV operators and UTMs. The safety improvement by the zoning approach becomes clearer in Figure 4, where distributions of the closest distance between two operating UAVs from the experiments are presented.
Figure 4 shows that the zoning approach always guarantees positive distance gaps between UAVs, which reduces the relevant collision avoidance efforts. On the other hand, the benchmark service strategies incur very close and even crossing UAV flights (i.e., zero distance gap). Recall that under the zoning approach, a flight path is generated within a zone, and thus it does not overlap with other paths in other zones. As collision avoidance is complex and might be infeasible when the distance between UAVs is tight, the safety net provided by the zoning approach is promising. In other words, the zoning approach can guarantee the safety of UAVs and the reliability of the UAV-based system, especially when large-scale UAV operations are considered.

4.3. Expected Service Quality to Demands by the Zoning Approach

The service quality for customers regarding UAV operations is another key factor that determines the success of a UAV-based service system. Given that immediate responses to demands determine service quality in many contexts, for emergency response in particular, we measure UAV response time to demands (i.e., the time interval between a service request receipt and a UAV arrival at the corresponding location). Figure 5 shows distributions of the mean response time over 20 simulations under the different problem classes and UAV deployment strategies.
The results shows that the zoning approach outperforms the other considered service strategies in terms of the mean response time for customers. This is because the benchmark strategies allow UAVs to serve distant demands, whereas the zoning approach restricts such behavior by limiting the UAV operation area. Naturally, long-distance travel increases the individual UAV workload and the likelihood of being busy. Under the scenario FCFS, where there is a waiting queue, such a practice significantly increases the response time for customers (see the response time differences between the FCFS and NQ scenarios).
It should be noted that while the zoning approach can avoid such long-distance and inefficient travels, it is true that a demand generated when the responsible UAV is busy will not be served under the zoning approach, even if there could be other UAVs available nearby. When there is no waiting queue, such a practice might result in many demand nodes being abandoned.
To verify this issue, we compute the percentage of demands that left the system without receiving service, with regard to the total number of demands generated in a simulation run. Figure 6 shows the results for scenario NQ. As shown in the figure, this negative impact by the zoning approach seems marginal, and interestingly, the zoning approach even serves more demands than the other strategies. This is due to the efficient use of UAVs and corresponding low utilization levels of the units.

4.4. Summary

For all the problem classes, the zoning approach outperforms the other considered UAV deployment strategies in terms of the safety of UAVs and the service quality for demands. The zoning approach shows that it can guarantee a sufficient gap between operating UAVs and that it can serve more demands at a faster rate than the other benchmark strategies. All of these findings are critical to implement a UTM with distributed workloads for collision avoidance and to provide acceptable service quality to customers.

5. Discussion

5.1. The Trade-Off between the Safety of UAVs and the Service Quality for Demands

We observed that the distance gap between flying UAVs becomes decreased when most of the demand nodes in a service area are densely located in the center of the area, which is natural considering the distribution of the demand nodes. If the safety of UAVs should be placed before the service quality to customers, one can consider further restricting the zoning approach. For example, adding a constraint that restricts the allocation of neighborhood demand nodes to different zones or treating the neighborhood demand nodes as abstract nodes could be considered for the zoning approach. Figure 7 illustrates two zoning solutions obtained with and without such additional constraints for UAV safety.
It should be noted that the zoning approach can also be implemented to maximize the service quality for demands. For example, one may want a zoning solution that minimizes the total distance between demand nodes and their responsible bases. The workload balance between zones can also be considered to derive a zoning solution.
Following this idea, we obtain different zoning solutions by applying the objective functions—to minimize the weighted total distance between demand nodes and bases and to minimize the between-zone variance of the total weighted distance between demand nodes and bases. We apply a genetic algorithm (GA) to derive the solutions. By the nature of a meta-heuristic algorithm, the implemented GA can easily address different types of objective functions and additional constraints (e.g., the limited flight time of UAVs) of the zoning problem. Please refer to Appendix A for details of the GA implementation. Figure 8 shows the solutions obtained; differences to the solutions in Figure 7 are clearly observed.
Importantly, the shift in the objective function of the zoning problem ( P z o n i n g ), which leads a different zoning solution, can bring a different degree of trade-off between UAV safety and service quality to demands. This phenomena is conceptually visualized in Figure 9.
In the figure, the performance of two different zoning solutions with different numbers of available UAVs is plotted. The solutions are distinguished by their line type (a solid line for a safety-oriented zoning solution and a dotted line for a service quality-oriented zoning solution), and their performances with respect to different perspectives are represented with different colors (blue for UAV safety and red for service quality for demands).
As illustrated in Figure 9, the UAV safety and the service quality for demands are indeed difficult maximize at the same time. The degree of the trade-off would also vary by the objective function applied to the zoning problem and the number of available UAVs. Therefore, it is important to properly formulate a target zoning problem and tune a solution algorithm for the zoning based on the priority, preference, and constraints of a target service system, so that the proposed approach can produce a valid and effective zoning solution. A whole process to successfully implement the zoning approach is illustrated in Figure 10.

5.2. Further Considerations for Zoning

The followings can be further considered for the practical implementation and improved performance of the zoning approach. First, the connectivity between zones is important to guarantee relatively easy transition between zones. If the bases of zones were placed outside of the zones, the connectivity would be guaranteed by a common and shared area acting as a flight corridor for crossing UAVs.
Next, the shape of zones can be considered for potential flight trajectories within a zone. For smooth and efficient movement within a zone, convexity of the zone would be desired. This can be guaranteed by known methods, such as convex decomposition of an area [33]. When there is a clear temporal pattern in demand arrivals, dynamic zoning that changes a zoning solution over time can be considered. In this case, keeping the relevant adjustments (e.g., frequency of updated zoning solution) at a minimum should be pursued.
Finally, aligned with the proposed and implemented solution for a UTM that separates airspace by altitudes, a three-dimensional zoning approach can be designed. This approach can provide flexibility in forming a zoning solution and scalability for increasing UAV operation volumes.

6. Concluding Remarks

Considering that the zoning approach is initially proposed to guarantee the safety of UAVs during operations, the relevant service quality degradation for customers is expected due to the restricted movement of UAVs by the zoning approach. Unlike this concern, however, the zoning approach shows a dominant performance in our experiments compared to the other current UAV deployment strategies in terms of both the safety of UAVs and the service quality for customers. This is accordance with Sung and Nielsen [18]’s observation, where they examine the zoning approach with a single UAV station.
We also observed the trade-off between the performance criteria (safety vs. service quality) in the experiments, a natural phenomena of UAV-based service systems. To meet a desired service level of a UAV-based system while addressing this trade-off, further assistance from the tactical part of the UAV operation (e.g., UAV trajectory planning optimization) and a well-tuned zoning solution algorithm based on the system’s priorities are essential for successful implementation of the zoning approach for a UAV-based service system.
Finally, let us highlight that the proposed zoning approach is a systemic solution for a UAV-based service system, which includes a tactical and operational solution for UAV deployment. The proposed approach does not require significant investments for a UTM, nor dramatic advances in UAV navigation and control technologies. Therefore, based on the demonstrated performance of the zoning approach and its implementation simplicity for a UAV-based service system, we believe that the zoning approach is a breakthrough for currently limited UAV applications and their deployment at large scale.

Author Contributions

Conceptualization, C.B.P., K.R., I.S. and P.N.; methodology, C.B.P., K.R., I.S. and P.N.; software, C.B.P. and K.R.; validation, C.B.P., K.R. and I.S.; writing—original draft preparation, C.B.P., K.R. and I.S.; writing—review and editing, I.S. and P.N.; visualization, C.B.P., K.R. and I.S.; supervision, I.S. and P.N. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Publicly available datasets were analyzed in this study. This data can be found here: https://github.com/Rosenkrands/zav.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Genetic Algorithm Implementation

We develop the GA such that it determines centroids of clusters from a predetermined set of candidate centroids in a service area. By doing so, a clustering solution can be derived while excluding the area where UAVs cannot fly (buildings, mountains, no-fly zones, etc.). With the area discretization, the zoning problem is to choose K number of centroids among a set of candidate centroids and to assign demand nodes to the selected centroids. To address this zoning problem with a discrete solution space, we implement the GA following the general purpose implementation presented by Scrucca [34].
A zoning solution is represented as a bit string for all candidate centroids, forming a chromosome of the GA. A value of one represents that a corresponding centroid is used for clustering; otherwise, it is zero. For the initial population we use 100 randomly generated chromosomes. The fitness for each chromosome is computed by the corresponding objective value. To generate the next population, the selection operator selects chromosomes from the current population following the probabilities, assigned to each chromosome of the population, inversely proportional to their fitness value. The selected chromosomes are further updated by applying the crossover operator with an 80% probability. The mutation operator that flips a bit of a chromosome is also applied to chromosomes with a probability of 10% in order to escape from a local optima.

References

  1. Shakhatreh, H.; Sawalmeh, A.H.; Al-Fuqaha, A.; Dou, Z.; Almaita, E.; Khalil, I.; Othman, N.S.; Khreishah, A.; Guizani, M. Unmanned aerial vehicles (UAVs): A survey on civil applications and key research challenges. IEEE Access 2019, 7, 48572–48634. [Google Scholar]
  2. Sung, I.; Choi, B.; Nielsen, P. On the training of a neural network for online path planning with offline path planning algorithms. Int. J. Inf. Manag. 2021, 57, 102142. [Google Scholar] [CrossRef]
  3. Bocewicz, G.; Nielsen, P.; Banaszak, Z.; Thibbotuwawa, A. Routing and scheduling of unmanned aerial vehicles subject to cyclic production flow constraints. In Proceedings of the International Symposium on Distributed Computing and Artificial Intelligence, Toledo, Spain, 20–22 June 2018; Springer: Cham, Switzerland, 2018; pp. 75–86. [Google Scholar]
  4. Murray, C.C.; Chu, A.G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transp. Res. Part C Emerg. Technol. 2015, 54, 86–109. [Google Scholar]
  5. Sah, B.; Gupta, R.; Bani-Hani, D. Analysis of barriers to implement drone logistics. Int. J. Logist. Res. Appl. 2021, 24, 531–550. [Google Scholar]
  6. Kim, S.J.; Lim, G.J.; Cho, J.; Côté, M.J. Drone-aided healthcare services for patients with chronic diseases in rural areas. J. Intell. Robot. Syst. 2017, 88, 163–180. [Google Scholar]
  7. Ghelichi, Z.; Gentili, M.; Mirchandani, P.B. Logistics for a fleet of drones for medical item delivery: A case study for Louisville, KY. Comput. Oper. Res. 2021, 135, 105443. [Google Scholar] [CrossRef]
  8. Dang, Q.V.; Nielsen, I.E.; Bocewicz, G. A genetic algorithm-based heuristic for part-feeding mobile robot scheduling problem. In Trends in Practical Applications of Agents and Multiagent Systems; Springer: Berlin/Heidelberg, Germany, 2012; pp. 85–92. [Google Scholar]
  9. Huang, H.; Savkin, A.V.; Huang, C. Scheduling of a parcel delivery system consisting of an aerial drone interacting with public transportation vehicles. Sensors 2020, 20, 2045. [Google Scholar]
  10. European Aviation Safety Agency. Concept of Operations for Drones: A Risk Based Approach to Regulation of Unmanned Aircraft; Technical Report; European Aviation Safety Agency: Cologne, Germany, 2015. [Google Scholar]
  11. Federal Aviation Administration. Unmanned Aircraft Systems (UAS) Traffic Management (UTM) Concept of Operation; Technical Report; U.S. Department of Transportation, Federal Aviation Administration: Washington, DC, USA, 2020.
  12. Radanovic, M.; Omeri, M.; Piera, M.A. Test analysis of a scalable UAV conflict management framework. Proc. Inst. Mech. Eng. Part G J. Aerosp. Eng. 2019, 233, 6076–6088. [Google Scholar] [CrossRef]
  13. Jiang, T.; Geller, J.; Ni, D.; Collura, J. Unmanned Aircraft System traffic management: Concept of operation and system architecture. Int. J. Transp. Sci. Technol. 2016, 5, 123–135. [Google Scholar]
  14. Xiangmin, G.; Renli, L.; Hongxia, S.; Jun, C. A survey of safety separation management and collision avoidance approaches of civil UAS operating in integration national airspace system. Chin. J. Aeronaut. 2020, 33, 2851–2863. [Google Scholar]
  15. Ballin, M.; Hoekstra, J.; Wing, D.; Lohr, G. NASA Langley and NLR research of distributed air/ground traffic management. In Proceedings of the AIAA’s Aircraft Technology, Integration, and Operations (ATIO) 2002 Technical Forum, Los Angeles, CA, USA, 1–3 October 2002; p. 5826. [Google Scholar]
  16. Dorling, K.; Heinrichs, J.; Messier, G.G.; Magierowski, S. Vehicle Routing Problems for Drone Delivery. IEEE Trans. Syst. Man Cybern. Syst. 2017, 47, 70–85. [Google Scholar] [CrossRef] [Green Version]
  17. Peng, K.; Du, J.; Lu, F.; Sun, Q.; Dong, Y.; Zhou, P.; Hu, M. A hybrid genetic algorithm on routing and scheduling for vehicle-assisted multi-drone parcel delivery. IEEE Access 2019, 7, 49191–49200. [Google Scholar]
  18. Sung, I.; Nielsen, P. Zoning a Service Area of Unmanned Aerial Vehicles for Package Delivery Services. J. Intell. Robot. Syst. 2020, 97, 719–731. [Google Scholar] [CrossRef]
  19. Otto, A.; Agatz, N.; Campbell, J.; Golden, B.; Pesch, E. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks 2018, 72, 411–458. [Google Scholar]
  20. Mukhamediev, R.I.; Symagulov, A.; Kuchin, Y.; Zaitseva, E.; Bekbotayeva, A.; Yakunin, K.; Assanov, I.; Levashenko, V.; Popova, Y.; Akzhalova, A.; et al. Review of Some Applications of Unmanned Aerial Vehicles Technology in the Resource-Rich Country. Appl. Sci. 2021, 11, 10171. [Google Scholar]
  21. Fu, J.G.M.; Bandyopadhyay, T.; Ang, M.H. Local Voronoi decomposition for multi-agent task allocation. In Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, 12–17 May 2009; IEEE: Piscataway, NJ, USA, 2009; pp. 1935–1940. [Google Scholar]
  22. Miao, X.; Lee, H.S.; Kang, B.Y. Multi-cleaning robots using cleaning distribution method based on map decomposition in large environments. IEEE Access 2020, 8, 97873–97889. [Google Scholar]
  23. Xiao, S.; Tan, X.; Wang, J. A simulated annealing algorithm and grid map-based UAV coverage path planning method for 3D reconstruction. Electronics 2021, 10, 853. [Google Scholar]
  24. Zhou, Q.; Lo, L.Y.; Jiang, B.; Chang, C.W.; Wen, C.Y.; Chen, C.K.; Zhou, W. Development of Fixed-Wing UAV 3D Coverage Paths for Urban Air Quality Profiling. Sensors 2022, 22, 3630. [Google Scholar]
  25. Ding, G.; Berke, A.; Gopalakrishnan, K.; Degue, K.H.; Balakrishnan, H.; Li, M.Z. Routing with Privacy for Drone Package Delivery Systems. arXiv 2022, arXiv:2203.04406. [Google Scholar]
  26. Hayat, S.; Yanmaz, E.; Muzaffar, R. Survey on unmanned aerial vehicle networks for civil applications: A communications viewpoint. IEEE Commun. Surv. Tutorials 2016, 18, 2624–2661. [Google Scholar]
  27. Amazon Prime Air. Revising the Airspace Model for the Safe Integration of Small Unmanned Aircraft Systems; Technical Report; Amazon Prime Air: Seattle, WA, USA, 2015. [Google Scholar]
  28. Feng, D.; Yuan, X. Automatic construction of aerial corridor for navigation of unmanned aircraft systems in class G airspace using LiDAR. In Airborne Intelligence, Surveillance, Reconnaissance (ISR) Systems and Applications XIII; International Society for Optics and Photonics, SPIE: Bellingham, WA, USA, 2016; Volume 9828, pp. 133–140. [Google Scholar] [CrossRef]
  29. Chang, Y.S.; Lee, H.J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst. Appl. 2018, 104, 307–317. [Google Scholar]
  30. Gu, Q.; Fan, T.; Pan, F.; Zhang, C. A vehicle-UAV operation scheme for instant delivery. Comput. Ind. Eng. 2020, 149, 106809. [Google Scholar]
  31. Deng, X.; Guan, M.; Ma, Y.; Yang, X.; Xiang, T. Vehicle-Assisted UAV Delivery Scheme Considering Energy Consumption for Instant Delivery. Sensors 2022, 22, 2045. [Google Scholar]
  32. Hartigan, J. Clustering Algorithms; Wiley: Hoboken, NJ, USA, 1975. [Google Scholar]
  33. Nielsen, L.D.; Sung, I.; Nielsen, P. Convex decomposition for a coverage path planning for autonomous vehicles: Interior extension of edges. Sensors 2019, 19, 4165. [Google Scholar]
  34. Scrucca, L. GA: A Package for Genetic Algorithms in R. J. Stat. Softw. 2013, 53, 1–37. [Google Scholar] [CrossRef] [Green Version]
Figure 1. Different service area configurations by the different UAV deployment strategies: (a) zoning; (b) closest; (c) closest with thresholds.
Figure 1. Different service area configurations by the different UAV deployment strategies: (a) zoning; (b) closest; (c) closest with thresholds.
Drones 06 00157 g001
Figure 2. The distributions of demands: (a) demand distribution U; (b) demand distribution C.
Figure 2. The distributions of demands: (a) demand distribution U; (b) demand distribution C.
Drones 06 00157 g002
Figure 3. The 5th percentile of the distances between operating UAVs: (a) demand distribution U; (b) demand distribution C.
Figure 3. The 5th percentile of the distances between operating UAVs: (a) demand distribution U; (b) demand distribution C.
Drones 06 00157 g003
Figure 4. The worst case proximity between operating UAVs: (a) demand distribution U; (b) demand distribution C.
Figure 4. The worst case proximity between operating UAVs: (a) demand distribution U; (b) demand distribution C.
Drones 06 00157 g004
Figure 5. The mean response time to demands: (a) demand distribution U; (b) demand distribution C.
Figure 5. The mean response time to demands: (a) demand distribution U; (b) demand distribution C.
Drones 06 00157 g005
Figure 6. The percentage of demand loss under scenario NQ: (a) demand distribution U; (b) demand distribution C.
Figure 6. The percentage of demand loss under scenario NQ: (a) demand distribution U; (b) demand distribution C.
Drones 06 00157 g006
Figure 7. Zoning solutions with and without additional safety constraints: (a) with safety constraints; (b) without safety constraints.
Figure 7. Zoning solutions with and without additional safety constraints: (a) with safety constraints; (b) without safety constraints.
Drones 06 00157 g007
Figure 8. Illustrations of zoning solutions with the service quality-oriented objective functions: (a) a solution to minimize the total distance between demands and bases; (b) a solution to evenly distribute demands to bases.
Figure 8. Illustrations of zoning solutions with the service quality-oriented objective functions: (a) a solution to minimize the total distance between demands and bases; (b) a solution to evenly distribute demands to bases.
Drones 06 00157 g008
Figure 9. The performance trade-off between different zoning solutions.
Figure 9. The performance trade-off between different zoning solutions.
Drones 06 00157 g009
Figure 10. A process for zoning approach implementation.
Figure 10. A process for zoning approach implementation.
Drones 06 00157 g010
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Pedersen, C.B.; Rosenkrands, K.; Sung, I.; Nielsen, P. Systemic Performance Analysis on Zoning for Unmanned Aerial Vehicle-Based Service Delivery. Drones 2022, 6, 157. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6070157

AMA Style

Pedersen CB, Rosenkrands K, Sung I, Nielsen P. Systemic Performance Analysis on Zoning for Unmanned Aerial Vehicle-Based Service Delivery. Drones. 2022; 6(7):157. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6070157

Chicago/Turabian Style

Pedersen, Casper Bak, Kasper Rosenkrands, Inkyung Sung, and Peter Nielsen. 2022. "Systemic Performance Analysis on Zoning for Unmanned Aerial Vehicle-Based Service Delivery" Drones 6, no. 7: 157. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6070157

Article Metrics

Back to TopTop