# Three-Dimensional Trajectory Optimization for UAV-Based Post-Disaster Data Collection
## 4 Numerical Analysis Methods
### Genetic Algorithm for Placement of Hovering Points  
To fundamentally solve the problems of traditional clustering methods, we transform the hovering point placement problem to a location set covering problem (LSCP) [37], which is commonly used to solve the placement problems of public facilities. The definition of the LSCP is given as follows:  
\[\min.\quad\sum_{j\in J}x_{j} \tag{8}\]  
\[\text{s.t.}\quad 1\leq\sum_{j\in J}a_{ij}x_{j}\qquad\forall i\in I \tag{9}\] \[x_{j}\in\{0,1\}\qquad\forall j\in J \tag{10}\]  
\[a_{ij}=\left\{\begin{array}{ll}1&\text{(if distance between $i$ and $j\leq$ coverage radius)}\\ 0&\text{(if distance between $i$ and $j>$ coverage radius)}\end{array}\right. \tag{11}\]According to the definition of the LSCP, the problem can be described as searching for the minimum number of hovering points that enable the coverage of all UEs in a certain area. The coverage radius of the facility is defined as the maximum coverage radius of the UAV, which is 62.132 m, based on the limitation of the UAV's flight altitude in this article.  
Figure 7: UE Clustering by K-means: (**a**) \(k=2\) (**b**) \(k=4\) (**c**) \(k=6\) (**d**) \(k=8\) (**e**) \(k=10\) (**f**) \(k=12\).  
The basic strategy to solve the LSCP in this article is the greedy algorithm, which continues to select the location of the hovering point that can cover the largest number of UEs until all UEs have been covered. In the LSCP, the minimum set of hovering points that cover all UEs needs to be determined, and the greedy algorithm can provide an approximate solution with relatively low computational complexity, taking into account the post-disaster scenarios in this paper.  
Although the method that calculates all candidate points is simple for implementation, a large number of candidates are needed to obtain an accurate solution, requiring huge amounts of calculations.  
Therefore, in this section, we use the genetic algorithm (GA) to search for the optimal locations for hovering points. In this paper, the GA is used to efficiently search for optimal hovering points that cover the maximum number of UEs while maintaining manageable computational complexity. Compared to exhaustive search, which requires evaluating a large number of candidate points, especially in a three-dimensional range, where the number of candidates would significantly increase when the size of the mission area is enlarged, GA provides an approximate solution with less computational complexity and effectively avoids local optima. The genetic algorithm is a search algorithm based on the principles of biological evolution, incorporating genetic operations such as selection, crossover, and mutation.  
**Selection**  
Roulette wheel selection is adopted for selection. The probability of the individual \(i\) being selected \(P_{i}\) is given as follows:  
\[P_{i}=\frac{f_{i}}{\sum_{j=1}^{N}f_{j}} \tag{12}\]  
where \(f_{i}\) is the fitness function of \(i\), which is defined as the number of UEs that can be covered from the location indicated by \(i\). Parents of the next generation are selected according to the magnitude of the fitness function. Individuals with better fitness functions are more likely to survive in the next generation.  
**Crossover**  
Blend crossover (BLX-\(\alpha\)) [38] is adopted for crossover, with a crossover rate of 0.9. As shown in Figure 8, the coordinates of child individuals are generated in the area decided by the coordinates of parent individuals and the parameter \(\alpha\). If we assume the coordinates of parent individuals are \((x_{1}^{p},y_{1}^{p})\), \((x_{2}^{p},y_{2}^{p})\), the coordinates of child individuals \((x_{1}^{x},y_{1  
where \(dx\), \(dy\), \(x_{\max}\), \(x_{\min}\), \(y_{\max}\), \(y_{\min}\) are given as follows:  
\[dx =|x_{1}^{p}-x_{2}^{p}| \tag{17}\] \[dy =|y_{1}^{p}-y_{2}^{p}|\] (18) \[x_{\max} =\max(x_{1}^{p},x_{2}^{p})\] (19) \[x_{\min} =\min(x_{1}^{p},x_{2}^{p})\] (20) \[y_{\max} =\max(y_{1}^{p},y_{2}^{p})\] (21) \[y_{\min} =\min(y_{1}^{p},y_{2}^{p}) \tag{22}\]