# Optimization Dubins Path of Multiple UAVs for Post-Earthquake Rapid-Assessment
## 3 HGSA Algorithm
### Mutation
### Simulated Annealing

The core idea of SA is to generate multiple neighborhood solutions by disturbing the current solutions. The algorithm needs to maintain a suitable balance between disturbing the existing solutions and keeping the good parts of the existing solutions. After the iterative optimization of the GA, we consider that the initial solution \(C\). _best_ has found a better UAV routing scheme that selects the appropriate targets to access and that determines the UAV access order and heading angle when accessing these targets. The main goal of SA is to fine-tune \(C\). _best_ to increase the expected profit for the routing scheme by adding or replacing a certain access target. In this paper, a disturbance strategy based on the profit distance ratio \(R_{rd}\) is designed with the following calculation

\[R_{rd}=\frac{\Delta w_{i}}{\Delta d_{i}},\forall i\in\mathbf{T}, \tag{15}\]

where \(\Delta w_{i}\) is the increase in the profit and \(\Delta d_{i}\) represents the additional distance after adding target \(i\) to the routing scheme. In this paper, two disturbance strategies are designed for the MURARP:

Disturbance strategy 1: Insert a target. Randomly select a gene site, and then find a target to maximize \(R_{rd}\) after insertion, which means inserting a target with the highest possible weight at the lowest possible cost. Disturbance strategy 2: Replace a target. Randomly select a gene site, and then find a target to maximize \(R_{rd}\) after replacing the current target. The main purpose of these disturbance strategies is to improve the expected profit of the routing scheme by maximizing the additional profit per distance. One of the above two strategies will be randomly used to generate a new solution in each annealing operation, and then the operations described in Section 3.1.3 should be performed on the new solution. Finally, the metropolis criterion is used to accept the new solution with a certain probability. ## 4 Experiments and Discussions

Since the MD-RDTOP-VP model is a generalization of the classic TOP, the former can be simplified to the traditional TOP model by special processing, and the model and algorithm of this paper can be tested by using the TOP's benchmark instances. In Section 4.1, we use the classic TOP's benchmark instances to carry out two numerical experiments, in which the first experiment shows the impact of the UAV turning radius on the collected profit and the second experiment shows the impact of heading angle discretization. In Section 4.2, according to the characteristics of the post-earthquake rapid assessment, we generate 42 simulation instances by transforming six sets of TOP benchmark instances. Then, the MD-RDTOP-VP model is used to solve these instances by the HGSA algorithm, and the relevant analysis is carried out. Finally, we conducted a case study based on real data as described in Section 4.3 to illustrate the application of our method in real-life scenarios. All experiments were carried out using a desktop computer with a single core of i5-6500 3.2 GHz CPU. Since the performance of the algorithm can be improved by properly setting the values of parameters [38], we refer to the parameter setting methods of related literatures [32; 33; 34], and consider the actual requirements of the MURARP problem to set the key parameters of the HGSA algorithm. The key parameters of the HGSA algorithm are as follows:

1. Population size \(N_{P}\) = 100;
2. Generation gap \(Gap\) = 0.8;
3. Mutation probability \(P_{M}\) = 0.3;
4. Initial temperature \(T_{0}\) = 100, termination temperature \(T_{end}\) = 0.1 and cooling rate \(R_{T}\) = 0.9;
5. Annealing iteration number \(N_{SA}\) = 100 times.