2.1. UAV Distribution Modes

The research in this area can be divided into UAV group distribution, vehicle and UAV collaborative distribution, vehicle and UAV parallel distribution, vehicle-supported UAV distribution, UAV-supported vehicle distribution, and mixed-mode distribution [9]. A schematic diagram of the first five UAV distribution modes is shown in Figure 1. The UAV group distribution only uses UAV to deliver goods as shown in Figure 1(a). The vehicle and UAV cooperative distribution is a common mode in research on vehicle and UAV combined distribution. The vehicle will be equipped with one or more UAVs, which store goods and provide charging services for UAVs during the distribution process as shown in Figure 1(b). And they deliver goods to their respective customer nodes under cooperation [10]. The parallel distribution of vehicles and UAVs mode denotes that the distribution of vehicles and UAVs is independent [11] as shown in Figure 1(c). The UAVs travel to and from the distribution center alone and are only allowed to pick up goods and charge at the distribution center [12, 13]. In the distribution mode of the vehicle-supported UAV, as shown in Figure 1(d), the vehicle serves as an auxiliary to provide goods storage and charging services for helping the UAV perform distribution tasks [13–15]. UAVs shuttle between vehicles and customer points for distributing goods to customers. At the same time, the vehicle drives to the next docking point or stops at the same spot, expecting the UAV to fly back after delivery. In the vehicle distribution mode supported by UAV as shown in Figure 1(e), UAV replenishes the vehicle as an auxiliary to assist the vehicles in performing the distribution tasks [16]. The hybrid model refers to utilizing two or more distribution modes to provide distribution services for customer nodes [17, 18]. As UAVs are continuously used in actual scenarios, the load-bearing capacity and endurance of UAVs will be greatly improved. So although there are many UAV distribution modes at present, pure UAV group distribution will become a large-scale mode to reshape future transportation and logistics, promote the 3D flexible use of airspace, and become a potential game changer in solving urban air traffic challenges [19].

2.2. UAV Group Path Planning

The goal of UAV group path planning is to find a sequence of waypoints connecting the starting point and the destination for each UAV as shown in Figure 2. Generally, the process of generating UAV paths is generated first through proactive planning [20] and then generated through reactive planning during execution [21–23]. Proactive planning focuses on resource scheduling and efficiency, while reactive planning focuses on task execution and safety. The UAV paths generated in proactive planning ensure that the objectives of the planned mission are achieved under predetermined changes in environmental parameters [8]. Reactive planning needs to consider that the route generated during the actual mission execution needs to be adjusted according to real-time changes in the environment. The research content of this article focuses on proactive planning. The common approach taken by most research on proactive planning starts around building a mathematical model of UAV group path planning. In the process of building the model, the environmental constraints, self-constraints, and intracluster constraints of the UAV group are taken into account [24, 25]. The construction methods of its environmental space mainly include the cell method, the landmark method, and the potential field method [26]. The path planning of this problem usually needs to construct the corresponding objective function according to different task requirements or decision-maker preferences [27]. The self-constraints of UAV group path planning are generally turning angle constraints, flight speed constraints, flight altitude constraints, climb angle constraints, dive angle constraints, and so on. Gao [28] presents a multiobjective optimization model for cooperative mission assignment of heterogeneous UAVs that balances mission gains against the risk of UAV losses. Surprisingly, it is noted that existing literature does not consider the impact of runway number limitations on UAV take-off in UAV delivery. This leads to safety considerations for UAVs during take-off, requiring a safe take-off time interval between UAVs.

2.3. Weather Conditions

Weather is a key feature to consider when flying a UAV, as it can affect the speed, distance, and safety of the UAV. In addition, the safety and efficiency of UAV logistics distribution are closely related to the weather conditions. Among them, strong wind, heavy precipitation, and ice accumulation have the most significant impact on flight safety. In bad weather, the probability of damage to UAVs during work increases sharply, bringing significant economic losses to enterprises. DHL, a German freight company, considered using a UAV to deliver a package weighing up to 2 kg. Still, finally, they reluctantly postponed the plan because of weather factors like sudden temperature drops and heavy snow. Therefore, it is of great theoretical and practical significance to schedule the logistics distribution route of UAVs according to the meteorological prediction data. Some literature studies how to accurately predict weather factors that affect UAV flight, such as wind speed and solar radiation [29, 30]. And some literature studies atmospheric temperature and how to affect the energy consumption of UAV batteries [31–33]. Stevens [34] studied how UAV operations may be affected by weather. Peng and Murray [11] considered the impacts from winds and rainfalls that change drones’ preferable/available travel time. Some studies on UAV path planning assume that wind can be static and consistent [35, 36], while others assume that wind can be dynamic and known in advance [31, 33, 37, 38]. Cheng et al. proposed a two-period UAV scheduling model considering stochastic weather, and their use of robust optimization for decision-making can mitigate the risk of delivery delays due to weather uncertainty [39]. In real-life scenarios, UAVs are prohibited from passing through the flight area during this period due to bad weather such as rainfall exceeding the safety threshold as shown in Figure 2. Therefore, when planning the route of the UAV, it is important to avoid passing through these no-fly areas. However, in the existing literature, no literature has not been found that consider converting weather data into flyable area data for UAVs for route planning.

2.4. Solution Methods

Due to the NP-hard nature of the UAV group path planning problem, the solution methods used in the existing literature include MLP [40, 41], declarative modeling [20, 31, 42, 43], computer simulation [44, 45], machine learning [46], and heuristic algorithms [47]. Although there are so many solution methods, the mainstream algorithms used in most literature are mainly divided into classical algorithms [48, 49] and metaheuristic algorithms. Classic algorithms include search-based algorithms such as Dijkstra algorithm [50], A^∗ algorithm [51], and graph search method. Moro [52] has presented a modification of the A^∗ path planning algorithm for a fixed-wing UAV to significantly reduce energy consumption in wireless sensor networks by up to 20% for the UAV and 25% for the network through efficient data collection. These algorithms show good performance in single UAV path planning problems but are difficult to apply to large-scale, high-dimensional, multi-UAV path planning problems. On this basis, some scholars have done more in-depth research and use evolutionary algorithms to solve the problem [47]. Perez-Carabaza et al. [53] studied the improved ant colony algorithm to solve the shortest time problem and stagnation problem of UAV flight trajectory. Rivera et al. [54] studied a superheuristic permutation multiobjective evolutionary algorithm based on ant colonies, integrating preferences into multiobjectives to solve the model. Ni et al. [55] integrated the ant colony algorithm with the neural network algorithm to improve the efficiency of solving three-dimensional paths. These algorithms have high search efficiency and can obtain the optimal solution in a static small global environment [56]. However, as map information increases, search nodes increase significantly, and the route planning problem becomes a large-scale and complex problem, which will make the algorithm calculation time longer [57]. Wang et al. [58] dispatched trajectory planning on flight decks by using hybrid A^∗ for initial path generation. Wang et al. [59] combined an artificially guided hybrid A^∗ algorithm for initial coarse path searching with an optimization approach for fine-tuning for docking trajectory planning of unmanned surface vehicles. When solving these large-scale problems, the performance and results of evolutionary algorithms are often unstable and cannot give a stable result within a limited time. In addition, there are also some cutting-edge studies using reinforcement learning to solve these problems [60, 61]. Wang et al. [62] offered a comprehensive review of deep reinforcement learning for UAVs to win dogfights. However, reinforcement learning usually requires that the state space should not be too large, but the UAV path delivery problem itself is a problem with a very large state space. Every UAV route, whether it is feasible or not, is a state. So when the search space of paths is slightly larger, the number of paths will fall into a combinatorial explosion. At the same time, the output results of reinforcement learning cannot be guaranteed to satisfy all strong constraints. This requires a repair module to ensure that the results are feasible, but the stability and optimality of the results cannot be guaranteed. Through the above description, each type of solution method has its advantages and disadvantages, and it is difficult to achieve both short calculation time and stable calculation results. Path planning requires constantly querying nodes in the time–space data, inserting and deleting them, and finally forming a route. Therefore, most classical algorithms and metaheuristic algorithms have one thing in common, which is that they require a large amount of calculations to find the shortest path between two points. The work of finding the shortest path between two points can be calculated in advance during the first calculation so that subsequent calculations can reuse the previous work and avoid the time-consuming caused by repeated calculations. In the existing research, no scholars have been found who have proposed a method that combines the data preprocessing process of finding the shortest path between two points in advance with the classic algorithm. This approach would not only prevent redundant computations in subsequent calculations, thereby reducing total processing time, but it would also guarantee stability and optimality in the computational outcomes.

For the state-of-the-art most relevant to the research content of this article, please refer to [11]. In [11], the authors conduct a quantitative analysis of the impact of wind and rain on UAVs, studying a scenario of parallel delivery involving one truck and multiple UAVs. By converting these weather impacts into time-dependent UAV flight times and feasible flyable time windows, they provide a new perspective on how weather conditions affect the truck–UAV distribution system. Their research is concentrated on short-distance deliveries, assuming uniform weather data across the entire service area over a given period, without taking into account the potential variations in weather conditions in localized regions. In their model, each UAV or truck is capable of serving multiple customers within a single mission. The optimization focuses on the allocation of customers to the truck or UAVs and the sequence in which these customers are served. This paper explores the scenario of weather-aware long-distance deliveries conducted by a group of UAVs. The weather data for localized areas within the entire service region change over time, with each UAV designated to serve only one customer. But the optimization efforts in this study are directed toward fine-tuning the safe take-off time intervals for the UAV group and devising flight routes that adhere to weather safety constraints.

3.1. Problem Description

The problem studied in this article comes from a large logistics company exploring UAV applications. The company hopes to operate a fleet of UAVs for long-distance transport. The problem description is shown in Figure 3. The UAVs take off one after another from a fixed runway every morning and then fly to multiple destinations. Complex and changeable meteorological conditions will endanger the transportation safety of UAV. Therefore, they need to be able to plan the flight route of the UAV based on high-precision weather forecasts to avoid dangerous weather areas and reach the destination within the specified time limit. For the sake of facilitating description and modeling, this article divides the UAV flight area into small regional blocks based on the minimum area covered by the weather forecast. The symbols and notations used in the mathematical formulation are shown in Table 1.

The flight time U of the UAV in each regional block is the same. Each regional block at each period U corresponds with a specific node. With n nodes, there is a directed graph G = (N, A) that arc (i, j) ∈ A and N represents the node-set. And 1 denotes the starting node and n denotes the end node. The weather conditions at time node of each UAV p (p ∈ P) will vary with the time. At the node i, let $$ represent the wind speed value and $$ represent the rainfall value of the UAV p. Only when $$ is less than or equal to the maximum wind speed W and $$ is less than or equal to the maximum rainfall R, the UAV p be allowed to fly safely at the node i. As notations, $$ represents the time required for the UAV to fly from node i to node j, H represents the interval time of the take-off time between any two UAVs, and W_penalty denotes the penalty value for not finishing the distribution task. When y^p is 1, the UAV fails to complete the distribution task. Otherwise, it is 0. The objective is to find a way to minimize the total distribution cost of the system by planning distribution routes for the UAV group, which include the take-off time of each UAV, the order of visiting nodes, and the time of arriving at each node in the graph.

3.2. Model Establishment

The objective function (1) aims to minimize the distribution time of the UAV. Constraint (2) indicates whether the UAV completes the distribution task. Constraints (3) and (4) represent the constraint on the arc balance in the fundamental shortest path problem. Constraint (5) indicates the take-off time constraint among UAVs. Constraints (6) and (7) show that for the UAV p, if the rainfalls $$ and $$ are heavier than R, then $$, which means no UAV passes through node i and node j. Similarly, constraints (8) and (9) illustrate that for the UAV p, if the rainfalls $$ and $$ are heavier than R, then $$, which means no UAV passes through node i and node j. Constraints (10) and (11) indicate that if $$, the time for the UAV to reach a point j is greater than or equal to the time it departs from the node i plus the time consumed on the way from the node i to the node j. If $$, this constraint is relaxed. Finally, constraint (12) denotes a nonnegative constraint, and constraints (13) and (14) give 0-1 variable constraint. In this model, the value of M is set to 1000 times the value of U, M = 1000U.

4.1. Space–Time Network Representation

Unlike the on-road distribution, the distribution space of a UAV is not a road network connected by roads but a relatively open and free-flight space. For generating distribution lines, it is necessary to grid and digitize them first. The grid method used is a method of spatial modeling. It divides the delimited topographic map into units, employs grids of equal size to divide the space, and uses a grid array to represent the whole space.

The shortest path is obtained by searching the free space on this grid network. If the spatial size of one unit defined by the grid is smaller, the environmental information shown by the grid map will be pretty elaborated. However, it has a problem that more knowledge needs to be stored, which will increase the storage overhead and reduce the speed of path planning. In other words, the performance of real-time line planning is not guaranteed. On the contrary, if the spatial size of one unit is larger, the path planning speed will improve because less information is waiting for storage. However, the division of environmental data will encounter the onset of fuzzier, which is not conducive to planning effective paths. Therefore, there is a contradiction between solution speed and space–time cost for the path planning algorithm’s performance, so the unit area size selection is an essential factor. The unit area size selected in this paper follows the experimental data rules. The distribution area is divided into regional blocks according to the minimum range covered by the weather forecast. Each unit area’s length, width, and size are the same, and the flight time U of the UAV in each unit area is provided as the same. In the period U, the flying state of the unit area is determined by the wind speed and rainfall in this period. In other words, it can fly within the unit area in the T period when the wind speed and rainfall are less than the safety threshold, otherwise cannot. (x,  y,  t) is used to uniquely sign each unit area in a different time, which x represents the coordinate value in the x-axis direction, y represents the coordinate value in the y-axis direction, and t represents one period U. Different colors indicate another feasible state of the unit area, such as dark color denoting the infeasible area while light represents the free-flying space. The whole weather data example of one period is shown in Figure 5.

Illustration of Figure 5: The figure on the left and right illustrates the rainfall distribution and wind speed distribution in a single period in the coverage area. Colored areas represent that the rainfall and wind speed exceed the UAV flying safety threshold, while colorless areas indicate that they meet the threshold. In addition, if darker the color, the greater the rainfall and wind speed.

4.2. Connected Graph Construction

When constructing a connected network, the vertex is each unit area, and an edge is a line in which one unit area connects to the nearby unit area. Because of the up–down and left–right relationship between spaces, it is limited that each unit area can only be directly associated with its upper, lower, left, and right unit areas. Owning to the limitation of the time-continuous relationship, the unit area in the T period can only be connected with that in the following T period. Based on the above two connection limitations, the whole connected network is achieved by construction. The process of edge formation of a connected graph is shown in Figure 6.

Illustration for Figure 6: If the current cell area is (x,  y,  t), the cell area connected to the edge forming the connected graph is (x,  y,  t + 1), (x,  y + 1,  t + 1), (x,  y − 1,  t + 1), (x − 1,  y,  t + 1), and (x + 1,  y,  t + 1).

Considering that reducing the scale of the connected graph can speed up the algorithm’s search, some optimization methods for designing around the characteristics of the problem need to be proposed to reduce the edge construction of the connected graph. When the starting position O(x_o,  y_o) and the ending position D(x_d,  y_d) are determined, the theoretical minimum flight time t_theory from the start node to the end node is also determined, t_theory = |x_o − x_d| + |y_o − y_d|. Based on the theoretical minimum flight time t_theory, the connected graph can be clipped to delete some space–time nodes in advance.

In Figure 7(a), the blue point is the start space–time node O(x_o,  y_o,  t_o), and the space–time nodes around O(x_o,  y_o,  t_o) extend to other nodes to form some edges, and these edges will be some part of the connected graph. Because these edges do not meet the starting position restrictions, becoming a part of the UAV flight path is impossible so that excess edges can be removed. After cropping, the changed graph is shown in Figure 7(b).

In Figure 8(a), the green point is the end space–time node D(x_d,  y_d,  t_d), and the space–time nodes around D(x_d,  y_d,  t_d) extend to other nodes to form some edges, and these edges will be some part of the connected graph. T_min is the earliest departure time. When the expression t_n − |x₁ − x₂| − |y₁ − y₂| − T_min < 0 is satisfied, these edges can be removed. After cropping, the changed graph is shown in Figure 8(b).

For the intermediate space–time node M(x_m,  y_m,  t_i) to form some edges, some optimization methods are proposed to remove some invalid edges. T_max is the latest arrival time. When the expressions t_i − |x_m − x_o| − |y_m − y_o| < T_min or t_i + |x_m − x_d| + |y_m − y_d| > T_max is satisfied, these edges can be removed.

The density of a graph reflects the proportion of the actual number of edges to the total potential edges that could exist between all node pairs. For directed graphs, this maximum is N × (N − 1), with N representing the node count. Sparse graphs have significantly fewer edges than the maximum, typically on the order of O(N) or linear concerning the number of vertices. In contrast, dense graphs have an edge count nearing the maximum, generally on the order of O(N²). Graph density crucially affects the efficacy of shortest path algorithms, as it influences computational efficiency. Sparse graphs often yield faster computations due to their limited edge count, whereas dense graphs necessitate algorithms capable of efficiently managing a higher volume of edges without overly increasing computation time. Algorithms that minimize unnecessary edge evaluations perform better in sparse graphs, while those that can handle a higher edge volume are preferred for dense graphs. As detailed previously, this paper deals with a connected graph whose nodes are of a known quantity, with no more than 5 incoming or outgoing edges per node, contingent on meeting minimum safety criteria for rain and wind. By adjusting these safety thresholds, control over the graph’s density is exerted. Setting low safety thresholds results in a sparser graph, potentially leading to a scenario where nodes remain unconnected. In contrast, higher thresholds increase the graph’s density, potentially approaching the scenario where nearly every node is connected by 5 incoming and outgoing edges, with the edge count nearing 5N. Thus, the connected graph in this study is inherently sparse by design, and algorithms suited to such a structure are employed, including classical ones like Dijkstra’s algorithm and heuristic-based approaches like the A^∗ algorithm.

4.3. Route Search Combination Generation

Based on the space–time network connectivity graph corresponding to the UAV distribution area, different start and end space–time nodes will lead to excessive combinations of UAV distribution routes. A lot of route search combinations will slow down the total calculation time. So a route search combination generation is proposed to form the UAV route search combinations and filter out some infeasible combinations in advance. The specific implementation logic is shown below.

Without considering the weather factors, the shortest flying time of a UAV from the starting unit area O(x₁,  y₁,  t₁) to the destination unit area D(x₂,  y₂,  t₂) is |x₁ − x₂| + |y₁ − y₂|. So the range of t₁ is [T_min, T_max − |x₁ − x₂| − |y₁ − y₂|], and the corresponding range of t₂ is [t₁ + |x₁ − x₂| + |y₁ − y₂|, T_max]. Then, by traversing every value in the range t₁ when the UAV takes off and combining it with the range t₂, all the route search combinations $$ satisfying the time limit can be enumerated.

After the UAV take-off time t₁ is determined as $$, the corresponding route search combination can be selected and numerous mapped search pairs $$ with clear start and end space–time nodes can be created, $$, $$ representing the fixed flight time of the UAV in one unit area.

4.4. Binary Search Algorithm

If the shortest travel time of a UAV from the starting unit O(x₁,  y₁,  t₁) to the destination unit area D(x₂,  y₂,  t₂) is t^∗, there must be a feasible route with a travel time longer than t^∗. So in this paper, the binary search method is adopted to speed up the search for the mapped search pairs E and find the shortest feasible UAV distribution time $$ and viable route. The Algorithm 1 of the binary search is as follows:

4.5. CH Algorithm

When calculating the shortest path of a large-scale network graph, the Dijkstra algorithm is the most used path planning algorithm between two points. To further provide computational efficiency, the bidirectional Dijkstra algorithm is derived. However, the query efficiency of the algorithm is affected by the structural characteristics of the network graph and the distance between query nodes, which will occasionally reach second-level response but is considerably challenging to achieve the stable output of microsecond-level response. Then, the shortest path CH algorithm is an acceleration technology for finding the shortest path in the network graph that was first proposed by Weisberger et al. [63, 64]. By making full use of the characteristics of the network graph, it preprocesses the original graph first. It calculates the shortest path distance between some points in advance for the convenience of simplifying the number of edges of the network graph and supporting a fast query of the shortest path between two points.

CH algorithm includes path network graph preprocessing and shortest path query. Thanks to the network diagram structure of weather data being rarely updated, some calculations can be performed in advance and then queried. So the query time leaps to the millisecond level. This acceleration is realized by “shortcuts.” It connects the two nonadjacent vertices u to v, and its edge weight is the sum of weights on the shortest path from u to v. Finally, in the shortest path query, these “shortcuts” created in the preprocessing stage are used to improve the search efficiency by skipping the “unimportant” vertices.

4.5.1. Graph Preprocessing

The preprocessing of the CH algorithm generates a multilayer graph structure in that each graph node is in a separate layer. To achieve it, the CH algorithm selects nodes from low to high according to the priority of nodes to perform iterative vertex shrinkage. Each time “shrinking” a node, it will generate corresponding “shortcuts” and form an updated graph structure. To push the shrink operation, the shortest path between the shrink node and others needs to be calculated, “shortcuts” inserted for it, and then, the shrink node marked as processed. Shrinking does not delete the node, but the shrink nodes can be ignored in the rest of the shrinking process.

CH algorithm has proved that sorting the graph nodes in any order and then successively adding shortcuts can ensure the accuracy of the result. However, different sorting methods will have an impact on the efficiency of preprocessing and subsequent search queries. So the priority ordering of nodes should be designed according to the characteristics of the problem. The node shrinkage sorting method uses the priority queue, and the smallest element of the queue has the most shrinkage potential. Considering the characteristics of this problem, only when the wind speed and rainfall of a unit area do not meet the flight conditions, the connectivity of adjacent nodes will be affected, as shown in Figure 9(a). The cell regions C2 and B3 that do not meet flight conditions will form isolated nodes and lead to unbalanced access to neighboring nodes. Some particular points, such as A1, B1, C1, A4, B4, and C4, are unilateral in or out nodes of the whole space–time network. The unilateral in or out node only stores the edge of the outgoing or incoming edge. These above-mentioned nodes all affect the network connectivity, so the affected adjacent nodes should be compressed first and shortcuts to improve the network connectivity. A corresponding new node shrinkage priority weight is designed.

The priority weight value w_priority of node shrinkage is determined by the following indicators:

$$ ()

In the above formula, n_{node_degree_in} is the number of edges that enter the shrink node and n_{node_degree_out} is the number of edges that go out from the shrink node. By the priority weight values w_priority, the nodes in Figure 9 are compressed in the order shown in Figure 10.

Finally, after the graph preprocessing, some shortcuts are added to the original graph. The new graph is shown in Figure 9(b).

4.5.2. Shortest Path Query

The query phase of the CH algorithm adopts the bidirectional Dijkstra algorithm. In the search process, you can only search from the low-order nodes to the high-order nodes. When querying the shortest path phase, the two-way search conducts from the starting node and the target node and then extends through the “shortcuts” created in the preprocessing stage. One begins the forward search from the starting node, and the other launches the reverse search from the ending node. After the two searches collide in the same node, the shortest path is found, and the two-way search is terminated. Although the overall search process is like Dijkstra’s algorithm, it differs because the search is only for nodes whose shrinkage order is higher than the current node, meaning the search is only for upward-sloping edges. The pseudocode of the bidirectional Dijkstra Algorithm 2 for CH is as follows:

Algorithm 2: Bidirectional Dijkstra algorithm.
•  

  Require: the start node s and end node t

•  

  Ensure:

• 1.

  priority queues: Q_f, Q_b; sets: S_f, S_b; distance variable: cost

• 2.

  initialize: Q_f = ∅, Q_b = ∅, S_f = ∅, S_b = ∅, cost = MAX

• 3.

  Q_f⟵(s, d_f[s]), Q_b⟵(t, d_f[t]), S_f⟵s, S_b⟵t

• 4.

  whileQ_f ≠ ∅ and Q_f ≠ ∅do.

• 5.

   u⟵poll(Q_f), v⟵poll(Q_b)

• 6.

  S_f⟵u, S_b⟵v

• 7.

   forxinadj(u)

• 8.

    ifxnot inS_f and order[x] > order[u] and d_f[x] > d_f[u] + weight(u, x)then

• 9.

     d_f[x] = d_f[u] + weight(u, x)

• 10.

     Q_f⟵(x, d_f[x]), S_f⟵x

• 11.

    end if

• 12.

   end for

• 13.

   ifuinS_b and d_f[u] + d_b[u] < costthen

• 14.

    cost = d_f[u] + d_b[u]

• 15.

   end if

• 16.

   forxinadj(v)

• 17.

    ifxnot inS_b and order[x] > order[v] and d_b[x] > weight(x, v) + d_b[v]then

• 18.

     d_b[x] = weight(x, v) + d_b[v]

• 19.

     Q_b⟵(x, d_b[x]), S_b⟵x

• 20.

    end if

• 21.

   end for

• 22.

   ifvinS_f and d_f[v] + d_b[v] < costthen

• 23.

    cost = d_f[v] + d_b[v]

• 24.

   end if

• 25.

  end while

• 26.

  Return cost

The schematic diagram of the CH algorithm searching the shortest path is shown in Figure 11.

4.5.2.1. Search From C1 to B4

If calculating the shortest path from C1 to B4, it is important to get the upward graph from C1 and the upward graph from B4 at first. Because C1 is the latest shrinking node, there is no upward graph. The upward graph of B4 is shown on the left of Figure 11. In the first iteration, the forward search result is empty, and the reverse search result is B1- > B4 and C1- > B4. Finally, they meet at point C1 and the shortest path is found.

4.5.2.2. Search From A1 to B4

Similarly, the upward graph from A1 and the upward graph from B4 at first will be obtained. The final upward graph of A1 and B4 is shown on the right of Figure 11. In the first iteration, the forward search result is A1- > C4, A1- > B4, and A1- > A4, and the reverse search result is B1- > B4 and C1- > B4. Finally, they meet at point B4 and the shortest path is got.

When selecting an algorithm for finding the shortest path in a graph, it is crucial to consider the characteristics of the graph and the application requirements. CH shines in scenarios where a static graph is queried repeatedly, offering extremely fast results following an initial, intensive preprocessing phase. Despite this upfront computational and memory investment, CH remains a scalable choice for extensive, unchanging datasets. On the other hand, Dijkstra’s algorithm is celebrated for its simplicity and generality, applicable to a broad array of weighted graphs and especially well-suited for educational purposes or graphs with real-time updates. However, it may underperform in terms of speed on large or dense graphs compared to more sophisticated algorithms like A^∗, which leverages heuristics to expedite the search process. A^∗ can achieve optimal and efficient results with the right heuristic, although its performance depends heavily on the heuristic’s quality. Additionally, A^∗ may require significant memory overhead to maintain its priority queue, particularly in extensive search spaces. The choice between these algorithms—CH for its post-preprocessing speed on static graphs, Dijkstra for its simplicity and broad applicability, and A^∗ for its heuristic-driven efficiency—will ultimately depend on the implementation context, taking into account factors such as graph size, frequency of updates, and the availability of a reliable heuristic.

In this article, a large three-dimensional time-varying network is constructed from predicted weather data. Given that the weather forecast data change very slowly, the graph remains static for considerable lengths of time. Furthermore, when devising a UAV group distribution solution, it is necessary to conduct repeated trials and invoke the algorithm to produce the final plan. Taking into account the need for computational efficiency and the avoidance of redundant calculations, selecting CH as the algorithm for computing the shortest path between two points on a large scale is the most suitable choice.

4.6. Path Assignment Model

After generating the feasible distribution route set L of each UAV through the binary search algorithm, the next step is to select an optimal feasible combination from these routes as the optimal solution to the problem. Due to the restriction in the number of runways during UAV take-off, the generated solution must ensure that different UAVs meet the take-off interval time restrictions. This problem is a 0-1 assignment problem with few constraints, and the problem size is not large, so it is particularly suitable to be solved with a mathematical programming solver. Therefore, based on the feasible distribution line set L, this paper establishes the UAV path assignment model and quickly solves it through the solver to generate the final UAV distribution solution.

The objective function (16) represents minimizing the total distribution time of the UAV. Constraint (17) indicates that only one distribution route would be selected for one UAV. Constraint (18) indicates that the take-off time of different UAV distribution lines meets the minimum time interval constraint.

5.1. Experiment Data and Settings

This experiment is based on the desensitized predicted meteorological data from the British Meteorological Office. Some of the most important weather datasets produced by the Met Office are now available for free on Amazon Web Services. The GitHub repository (https://github.com/MetOffice/aws-earth-examples) contains example code of how to access these datasets. The predicted meteorological data include location coordinate information, weather time, wind speed, and rainfall. According to the minimum range covered by the weather forecast, the coverage area has been divided into 2 × 2 km regional blocks. Through the space–time network representation method of Section 4.1, each regional block can be uniquely represented by (x, y), where x represents the coordinate value in the x-axis direction, and y represents the coordinate value in the y-axis direction. The flight speed of UAVs that can be searched on the Internet ranges from about 60 km to 300 km per hour, which is equivalent to 1–5 km per minute. Considering that this paper mainly studies the impact of weather changes on the selection of safe flight routes by UAVs, the flight speed of the UAV under all weather conditions is assumed to remain unchanged and maintained at 1 km per minute and UAVs can only fly up, down, left, and right from the current area block to the next area block or stay on the spot. So the flying time in each area block U is fixed at 2 min. At a fixed time every day, some UAVs will start flying from the center to other destination areas. Refer to the minimum take-off interval between two aircraft at an airport searched on the Internet and limit that the minimal take-off interval time H between any two UAVs is 2 min. The experimental data consider two weather factors affecting the crash of UAV: wind speed and rainfall. Reference [65] searched for a complete list of the 500 most commonly registered UAVs and determined which UAVs could operate in wind and rain using information sources provided by the manufacturers. They explored weather-limited UAV flyability by comparing historical wind speed and rainfall data to manufacturer-reported thresholds of common commercial and weather-resistant UAVs with a computer simulation. The analysis showed the UAVs can withstand the maximum wind speed thresholds of 15 miles per second (m/s), which could significantly increase the UAVs’ maximum flight capabilities. So the max wind speed threshold W is set to 15 m/s. As stated online, UAVs should not be flown when rainfall exceeds 100 mm in 24 h. So the max rainfall threshold R is set to 4 mm per hour (mm/h). When the wind speed is greater than W or rainfall is greater than R, the UAV cannot fly in the coverage area and will be forced to fall.

The computer parameter configuration of these experiments is Intel (R) Core (TM) i5-2450m CPU @ 2.50ghz, and they are all running on the Windows Server 2016 operating system. The proposed algorithm is implemented by Java programming, and the Java JDK version is 1.8.0_172. The algorithm code is mainly used as a research tool to verify the theories and methods proposed in this paper, and it is not an independent software. In addition, the code uses two native Java libraries (Java Collections library and Java IO library) and a third-party library (Java version of CPLEX), without using any framework, which is sufficient to support our research and experimental needs. Specifically, the Java Collections library is used for data processing and algorithm logic implementation, the Java IO library for data reading and writing, and the Java version of the CPLEX library for building and solving the mathematical model proposed in this paper. The Java Collections library and the Java IO library are included with the Java JDK package, and the version of CPLEX is 12.7.

5.2. Correctness Verification and Analysis

The mathematical model of this problem is converted into a CPLEX program to evaluate the correctness of the model and algorithm. The experimental test data are Set1, a small-scale test data set that IBM ILOG CPLEX12.8 can solve. In the Set1 data, the maximum flight time is under 1 hour [09:00–10:00]. The arrival time to the destination node must be before 10:00. The city (141,327) was chosen as the starting point, and the four vertices of a square extending outward from the starting point were chosen as the destination points. A total of 5 days of data were selected, and the destination points in each data were successively chosen from 1 unit distance outward to 5 unit distances. So this will have 25 test cases in the Set1 data. The spatial distribution of the start and destination points is shown in Figure 12. The four vertices of the square marked with a gray grid are the destination points. Each case has 4 UAVs.

This paper sets the maximum computing time of CPLEX and the multistage dynamic optimization algorithm to 5 min. If the calculation is not completed within 5 min, both programs will terminate and give the current optimal solution. Then, the experimental analysis is carried out by comparing the calculation results of CPLEX and the algorithm. The data information and calculation results of Set1 data are summarized in Table 2.

Table 2 shows that the CPLEX results of the mathematical model are generally consistent with the algorithm’s results, which verify the correctness of the dynamic optimization algorithm. As shown in Figure 13, when the scale of the problem grows larger, the calculation time of CPLEX will increase accordingly. The average CPLEX calculation time is 5.6 s. However, the dynamic optimization algorithm is efficient and stable in small-scale examples. Its calculation time is 0.144 s, which is 38.8 times faster than the CPLEX time. Especially, when the problem size becomes larger, the difference in calculation time becomes larger and larger, and the maximum difference can be 248 times. This is because the CPLEX solver uses a general mathematical method to solve the problem. When the problem size becomes larger, the decision variables and constraints increase exponentially and the calculation time becomes longer. However, the algorithm is specifically designed for this problem, reducing a large amount of ineffective calculations, such as some invalid path searches. Therefore, it can solve larger-scale problems more efficiently than the solver. To assess whether the experimental results were statistically significant, a paired-sample t-test was performed on the calculation time, with the results being t = 3.8922 and p = 0.0006. This shows that there is a significant difference in the average computing performance between them at the set significance level α = 0.05. Statistical analysis shows that the algorithm has better average computing performance than CPLEX when using the same data set.

5.3. Effectiveness Validation and Analysis

To verify and analyze the effectiveness of the multistage dynamic optimization algorithm, the large-scale test data set Set2 was used for this experiment. At the same time, to verify the algorithm’s effectiveness, the shortest path A^∗ algorithm and Dijkstra algorithm applicable to this problem are implemented in this paper, and comparative testing and experimental analysis are carried out. The Set2 data pick the city (236,241) as the starting point, and all vertices on the edge of a square extending outward from the starting point were chosen as the destination points. In the Set2 data, the maximum flight time is under 7 hours [09:00–16:00]. The arrival to the destination node must be before 16:00. Similarly, a total of 5 days of data were selected, and the destination points in each data were successively chosen from 5 unit distances outward to 25 unit distances with an interval of 5 units each time. So this will also have 25 test cases in the Set2 data. The spatial distribution of the start and destination points is shown in Figure 14. The vertices of the square marked with a gray grid are the destination points. Among them, the largest test case has 200 UAVs.

The shortest path A^∗ algorithm is one of the vital heuristic algorithms, which is realized by the estimation function F = GW + HW, which GW represents the cost from the path point to the starting point and HW represents the Manhattan distance from the path point to the endpoint. The shortest path Dijkstra algorithm is one of the most classical algorithms, which relies on the graph structure data for breadth-first search to ensure that the value of the current node is optimal for the value of the previous layer. In the experiment, the algorithm flow of solving this problem remains unchanged. The distinction is to replace the CH algorithm with the A^∗ and Dijkstra algorithms, respectively, for the comparative test of the shortest path. The data information and calculation results of Set2 data are summarized in Table 3. In Table 3, column “EOV” denotes extending outward value, column “mini_x” denotes minimum x value, column “mini_y” denotes minimum y value, column “max_x” denotes maximum x value, column “mini_x” denotes maximum x value, and column “p” denotes the preprocessing time.

Table 3 and Figure 15 show the multistage dynamic optimization algorithm having an additional preprocessing time, which is very time-consuming and takes an average of 536.7 s. Fortunately, it is a one-time calculation time-consuming, providing efficient services for a large amount of subsequent new calculations or repeated calculations. When the scale of the problem is enlarged, the calculation time of the A^∗ and Dijkstra algorithms increases rapidly and changes dramatically. In contrast, the calculation time of the algorithm increases slowly and varies linearly. Without considering the preprocessing time, compared with the A^∗ algorithm and Dijkstra algorithm, the dynamic optimization algorithm can calculate the UAV group distribution solution faster. The average calculation time of the A^∗ algorithm is 592 s, and the Dijkstra algorithm is 557 s. However, the algorithm takes an average of 160 s, which is 3.69 times faster than A^∗ and 3.47 times more than Dijkstra. This can prove that the dynamic optimization algorithm has good solving efficiency and stability in large-scale examples. Because after the algorithm completes the preprocessing process, each subsequent shortest path calculation is almost equivalent to a fast table query, and the time consumption becomes stable and small. However, each shortest path calculation of A^∗ and Dijkstra is a completely new calculation and requires continuous querying, inserting, deleting nodes, and comparing weight values. Therefore, when the search network structure is determined, the greater the number of UAV, the better the effect of the dynamic optimization algorithm will be. In order to evaluate whether the experimental results are statistically significant, the three algorithms were grouped in pairs, and each group performed a paired-sample t-test on their computing time. The test results of the algorithm and A^∗ are t = −2.9413 and p = 0.0071, the test results of the algorithm and Dijkstra are t = −2.9364 and p = 0.0072, and the test results of A^∗ and Dijkstra are t = 2.9747 and p = 0.0065. These show that there is a significant difference in their average computing performance at the set significance level α = 0.05. Statistical analysis shows that when using the same data set, the algorithm has better average computing performance than A^∗ and Dijkstra.

A special point to note about this experiment is that the preprocessing time was not considered when calculating the runtime of the proposed algorithm. The experimental result data revealed that when the preprocessing time is taken into account, the proposed algorithm is on average 105 s slower than A^∗ and 140 s slower than Dijkstra. However, the preprocessing process is one-time and the resulting data can be used repeatedly. Through the analysis of existing experimental data, it can be found that the preprocessed result data only need to be reused once, and the calculation time of the proposed algorithm (536.7 + 160 ∗ 2 = 856.7) will be less than that of A^∗ (592 ∗ 2 = 1184) and Dijkstra (557 ∗ 2 = 1114) that are recalculated twice. As the preprocessed result data are reused more times, the algorithm will save more time. From this perspective, this still proves the effectiveness of the algorithm.

5.4. Parameter Sensitivity Analysis

The proposed method is designed based on a large-scale three-dimensional network structure. The size of the three-dimensional network structure will directly affect the overall calculation amount of the method. Therefore, any parameter that affects the size of the three-dimensional network structure will have an impact on the performance of the proposed method. It is acknowledged that the change in wind speed threshold and rainfall threshold will affect the structure of the network diagram, which will further influence the calculation of the overall algorithm. To analyze the practicability and performance of the algorithm in this paper, the parameter sensitivity analysis is carried out to study the impact of the change of wind speed threshold and rainfall threshold on the algorithm’s performance under different weather threshold conditions. The large-scale test data set Set3 was used for this experiment. In the Set3 data, except for wind speed threshold and rainfall threshold data, the other data information is the same as the Set2 data.

When analyzing the wind speed sensitivity, the rainfall threshold is fixed at 4, and the wind speed threshold ranges from 12.5 to 14.5 at an interval of 0.5. Similarly, a total of 5 days of data were selected. So there are 25 test cases for this experiment on wind speed sensitivity. The data information and calculation results of the Set3 data for wind speed sensitivity analysis are shown in Table 4. In Table 4, column “edge num” denotes the total edge number of the space–time network.

From the result data of Table 4 and Figure 16, it is found that in some test cases on the same day, when the threshold of wind speed gradually increased, the size of the network structure gradually increased, and the calculation time of the proposed algorithm increased accordingly. At the same time, there are some test cases on the same day showing that when the wind speed threshold gradually increases, the size of the network structures changes a little. And the calculation time of the proposed algorithm accordingly remains relatively stable.

When analyzing the rainfall sensitivity, the wind speed threshold is fixed at 15, and the rainfall threshold ranges from 1.5 to 3.5 at an interval of 0.5. Similarly, a total of 5 days of data were selected. So there are 25 test cases for this experiment on rainfall sensitivity. The data information and calculation results of the Set3 data for rainfall sensitivity analysis are shown in Table 5. In Table 5, column “edge num” denotes the total edge number of the space–time network.

From the result data of Table 5 and Figure 17, similar conclusions were found regarding the sensitivity to wind speed as those observed in the above experiments. The calculation time of the proposed method is positively related to the scale of the network structure. When the scale of the network structure becomes larger, the calculation time becomes longer. Likewise, when the size of the network structure changes slightly, the computation time does not change much.

It can be concluded from Figures 16 and 17 that the size of the network structure shows a strong positive correlation with the calculation time of the algorithm. When the scale of the network structure changes with the wind speed threshold and rainfall threshold, the calculation time of dynamic optimization calculation also changes, and there are no obvious abnormal fluctuations. When the wind speed threshold and rainfall threshold exceed specific values, there is no area where UAVs cannot fly and no change in the size of the network structure, and the corresponding calculation time tends to be stable. It turns out that the solving efficiency and stability of the dynamic optimization algorithm are strongly related to the size of the network structure, and the size of the network structure is strongly related to the wind speed threshold and rainfall threshold. Therefore, the performance of the proposed algorithm can be affected by adjusting the wind speed threshold and rainfall threshold. A feasible and safer solution can be found more quickly by lowering the wind speed threshold and rainfall threshold. The relationship between the specific sizes of these thresholds and the size of the network structure can be obtained through advanced data preprocessing operations.