# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 5 Computational Results
### Computational Results for CARP  
The performance of the metaheuristic algorithm was tested using differently sized problems from the instance sets gdb by [PERSON] (2007), val by [PERSON] et al. (2007), egl by [PERSON] (1998), kshs by [PERSON] et al. (2007), bmcv by [PERSON] et al. (2007), eglL by [PERSON] and [PERSON] (1998), and Hefei by [PERSON] and [PERSON] (2007). In particular, the largest and most complex problems from each instance set were used. The largest-sized problems in the gdb, val, egl, egl, kshs, bmcv, and eglL sets, and the Hefei-4 test problem from the Hefei set, in which a total of 1212 edges, 485 required edges, and 727 non-required edges were chosen. The solution quality of the suggested algorithm is presented as the deviation value from the optimal or the best known solution in the literature. \[f(s):\]  
The objective function value obtained by the proposed algorithm  
\[f(s^{*}):\]  
The objective function value of the optimal or the best known solution  
\[\text{Deviation value}\left(\text{Gap}\right)=\left(\frac{f(s)-f(s^{*})}{f(s^{*})}\right) \tag{3}\]  
The deviation value presented in Equation (3) is used as a performance indicator for the suggested method. On the other hand, the parameter values of the algorithm were determined as the initial temperature value \((T_{0})\), the final temperature value \(\left(T_{f}\right)\), and the cooling rate \((\infty)\) values \(\left(T_{0},\ T_{f},\ \infty\right)=(100,0.1,0.99)\). The number of iterations \((I)\) to be performed at each temperature was determined based on the problem size and is shown in Table 2.  
As presented in Table 2, the number of iterations is increased as the size of the problem increased in order to sufficiently explore the search space for each temperature value of the algorithm. The proposed algorithm for the CARP was coded using the Python 3.7 programming language and executed on an Intel Core i5 1.6 GHz computer with 8 GB RAM. The suggested algorithm was run 10 times for each test problem and the obtained results are presented in Table 3. \begin{table}
\begin{tabular}{c c} \hline \hline
**Number of Required Edges** & **Number of Iterations** \\ \hline \(E_{R}\leq 15\) & 50 \\ \(15<E_{R}\leq 45\) & 200 \\ \(45<E_{R}\leq 60\) & 500 \\ \(60<E_{R}\leq 75\) & 750 \\ \(75<E_{R}\leq 90\) & 1000 \\ \(90<E_{R}\leq 200\) & 2000 \\ \(200<E_{R}\leq 500\) & 5000 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Number of iterations in simulated annealing algorithm. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Test Problems** & \begin{tabular}{c} **Required Edges** \\ **(Total Edges)** \\ \end{tabular} & **Vehicles** & \begin{tabular}{c} **Results of the** \\ **Proposed Algorithm** \\ \end{tabular} & \
\begin{tabular}{c} **Optimal/The Best** \\ **Known Results** \\ \end{tabular} & **Gap** &
\begin{tabular}{c} **Computation** \\ **Times (Seconds)** \\ \end{tabular} \\ \hline kshs-6* & 15 (15) & 3 & 10197 & 10197 & - & 4 \\ gdb-5 & 26 (26) & 6 & 377 & 37 & - & 30 \\ gdb-21 & 33 (33) & 6 & 156 & 156 & - & 34 \\ gdb-22 & 44 (44) & 8 & 200 & 200 & - & 40 \\ gdb-23* & 55 (55) & 10 & 233 & 233 & - & 142 \\ val-5c & 65 (65) & 5 & 474 & 474 & - & 291 \\ val-5d & 65 (65) & 9 & 581 & 575 & 0.01 & 255 \\ bmcv-d1 & 79 (98) & 5 & 3235 & 3215 & 0.006 & 558 \\ bmcv-f24* & 86 (142) & 4 & 3240 & 3210 & 0.009 & 794 \\ val-10c & 97 (97) & 5 & 446 & 446 & - & 1104 \\ val-10d* & 97 (97) & 10 & 530 & 525 & 0.009 & 987 \\ egl-e4c & 98 (98) & 19 & 11631 & 11529 & 0.008 & 810 \\ bmcv-c18 & 121 (133) & 11 & 5640 & 5570 & 0.012 & 1102 \\ bmcv-d18 & 121 (133) & 6 & 4165 & 4165 & - & 1345 \\ egl-s4a & 190 (190) & 19 & 12456 & 12216 & 0.019 & 2440 \\ egl-s4b & 190 (190) & 27 & 16502 & 16201 & 0.018 & 2375 \\ egl-s4c* & 190 (190) & 35 & 21207 & 20476 & 0.035 & 2345 \\ eglL-g2a & 375 (375) & 22 & 1128386 & 1088040 & 0.037 & 7404 \\ eglL-g2e* & 375 (375) & 42 & 1663216 & 1606079 & 0.035 & 7386 \\ hefei-4 & 485 (1212) & 28 & 767684 & 737730 & 0.040 & 9295 \\ \hline \hline \end{tabular}
\end{table}