# Optimization Dubins Path of Multiple UAVs for Post-Earthquake Rapid-Assessment
## 3 HGSA Algorithm
### Mutation
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline _Instance_ & \(N\) & \(K\) & \(\mathbf{R_{MAX}}\) & \(\mathbf{R_{AVG}}\) & \(\mathbf{R_{MIN}}\) & \(\mathcal{CPU_{AVG}}\) \\ \hline _E2-12_ & 62 & 2 & 118.800 & 109.656 & 101.700 & 20.77 \\ _E2-13_ & 62 & 2 & 121.800 & 114.818 & 110.120 & 21.59 \\ _E2-14_ & 62 & 2 & 154.600 & 143.797 & 132.820 & 22.86 \\ _E2-23_ & 62 & 2 & 142.680 & 131.880 & 111.160 & 21.88 \\ _E2-24_ & 62 & 2 & 173.180 & 162.229 & 151.320 & 22.33 \\ _E2-34_ & 62 & 2 & 162.080 & 154.936 & 150.320 & 24.29 \\ _E3-123_ & 62 & 3 & 177.600 & 172.180 & 168.170 & 32.65 \\ _E3-124_ & 62 & 3 & 207.520 & 197.003 & 192.220 & 33.87 \\ _E3-134_ & 62 & 3 & 192.980 & 182.736 & 175.010 & 35.02 \\ _E3-234_ & 62 & 3 & 213.320 & 199.452 & 191.160 & 32.88 \\ _E4-1234_ & 62 & 4 & 245.580 & 237.628 & 221.368 & 45.57 \\ \hline _C2-12_ & 21 & 2 & 50.040 & 49.410 & 43.740 & 9.96 \\ _C2-13_ & 21 & 2 & 43.840 & 42.784 & 41.120 & 10.44 \\ _C2-14_ & 21 & 2 & 69.120 & 65.640 & 63.520 & 12.84 \\ _C2-23_ & 21 & 2 & 57.520 & 55.629 & 42.614 & 11.77 \\ _C2-24_ & 21 & 2 & 78.120 & 70.082 & 61.966 & 13.68 \\ _C2-34_ & 21 & 2 & 71.040 & 66.944 & 64.000 & 14.59 \\ _C3-123_ & 21 & 3 & 73.360 & 71.618 & 64.220 & 16.34 \\ _C3-124_ & 21 & 3 & 84.980 & 80.916 & 76.230 & 18.75 \\ _C3-134_ & 21 & 3 & 81.360 & 76.629 & 73.680 & 17.33 \\ _C3-234_ & 21 & 3 & 86.504 & 82.269 & 79.160 & 15.53 \\ _C4-1234_ & 21 & 4 & 94.088 & 89.204 & 84.286 & 25.20 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results for the 22 simulation experimentsThe relevant parameters values of the UAVs used by the rescue teams are shown in Table 7.

We modeled the above rapid assessment by using the MD-RDTOP-VP model and solving the problem with the HGSA algorithm. The results are shown in Table 8. A multi-UAV routing scheme is found within 10 s using the same parameters as in Section 4.2. In the routing scheme, the UAVs accessed 42 targets, of which 15 were revisited. The expected profit of the routing scheme is 253.540. Specifically, Table 8 records the number of visit targets, \(N_{VT}\), the number of revisit targets, \(N_{RT}\), the task execution time, \(T_{E}\), and the utilization rate, \(R_{U}\), of the UAV endurance. From the experimental results shown in Table 8, it can also be seen that the routing scheme generated by our model and algorithm maximizes the endurance utilization rate of each UAV under the premise of target revisit-allowed strategy. ## 5 Conclusions and Potential Future Work

In this paper, a novel routing problem for multiple-UAV post-earthquake rapid-assessment is presented. Considering endurance and kinematic constraints, a multi-depot launching heterogeneous \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Parameters** & **UAV 1** & **UAV 2** & **UAV 3** & **UAV 4** \\ \hline Speed (km/h) & 90 & 60 & 60 & 90 \\ Turning radius (m) & 200 & 100 & 100 & 200 \\ Endurance (min) & 60 & 30 & 30 & 60 \\ Error of sensors (\%) & 0.1 & 0.2 & 0.1 & 0.2 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Relevant parameters values of the UAVs used by the rescue teams \begin{table}
\begin{tabular}{c c c c} \hline \hline
**UAV** & \(N_{VT}\) & \(N_{RT}\) & \(T_{E}\) & \(R_{U}\) \\ \hline UAV1 & 27 & & 59.71 & 99.52\% \\ UAV2 & 2 & & 29.93 & 99.77\% \\ UAV3 & 3 & & 29.84 & 99.47\% \\ UAV4 & 25 & & 59.94 & 99.90\% \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Results of the case examples

Figure 9: Potential targets and UAV depots of the Jiuzhaigou earthquake. UAVs rapid-assessment routing scheme is optimized with the objective of maximize the expected profit. We also specifically design a two-stage hybrid heuristic algorithm, called HGSA, to solve this problem and three sets of experiments are carried out to verify the performance of the HGSA. The experimental results indicate that the HGSA algorithm can obtain a high-quality solution of MURARP stably. For future research, the problem introduced in this paper can be further studied from two aspects.