# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 5 Computational Results
### Computational Results for MS-DARP-DD  
Seven different test problems were generated for the DARP-DD, and the obtained results for these problems were presented in the previous section. The multiple service drone arc routing problem with deadheading demand (MS-DARP-DD), one of the special cases of the DARP-DD that involves servicing the required edges more than once, is discussed in this section. A multiple service condition was added to some required edges in the DARP-DD test problems. Thus, MS-DARP-DD test problems were generated. The proposed metaheuristic algorithm was applied to solve these problems. The parameter values of the algorithm were the same as for those determined in the DARP-DD. The suggested algorithm was run 10 times for each test problem and the best obtained solutions are presented in Table 7. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**DARP-DD**} & \multicolumn{3}{c}{**MS-DARP-DD**} \\ \cline{2-7}
**Test** & \multirow{2}{*}{**Required**} & **Number of** & **Results** & **Number of** & **Results** & **Computation** \\
**Problems** & & **Drones** & **(Objective** & **Edges** & **(Drone** & **Function** & **Times** \\  & **Edges** & **Capacity**) & **Values**) & & **Capacity** & **Values**) & **Computation** \\ \hline DARP-1 & 17 & 4 (500 J) & 1204.46 & 21 & 5 (500 J) & 1417.3 & 32.5 \\ DARP-2 & 28 & 4 (1000 J) & 2429.58 & 32 & 5 (1000 J) & 2707.22 & 70.2 \\ DARP-3 & 44 & 6 (1000 J) & 3287.91 & 51 & 7 (1000 J) & 3719.41 & 210.3 \\ DARP-4 & 64 & 5 (1500 J) & 3915.78 & 69 & 5 (1500 J) & 4067.02 & 580.4 \\ DARP-5 & 84 & 7 (1500 J) & 6238.37 & 91 & 8 (1500 J) & 6649.84 & 834.9 \\ DARP-6 & 100 & 8 (1500 J) & 6916.44 & 107 & 9 (1500 J) & 7123.38 & 1350.7 \\ DARP-7 & 200 & 21 (1500 J) & 20137.3 & 207 & 21 (1500 J) & 20724.5 & 3750.9 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Obtained results for MS-DARP-DD test problems. Figure 6: Drone routes obtained for DARP-DD-1. Table 7 presents the obtained results for the DARP-DD, where each required edge must be serviced once, and the MS-DARP-DD, where some required edges must be serviced more than once. For example, in the DARP-2 problem for the DARP-DD, there are 28 required edges on the graph and each required edge must be serviced once. When this problem was solved with the suggested algorithm, the 28 required edges on the graph were serviced by four drones with an energy capacity of 1000 Joules and the total traveled distance was obtained as 2429.58 units. On the other hand, if the DARP-2 problem is considered for the MS-DARP-DD, there are 32 required edges on the graph with a multiple service condition providing service twice for edge (\(14-15\)), twice for edge (\(19-20\)), three times for edge (\(2-3\)), and once for the other required edges on the graph. The suggested algorithm was also used to solve this problem. The obtained results show that the 32 required edges on the graph were serviced by five drones with an energy capacity of 1000 Joules and the total traveled distance by the drones was obtained as 2707.22 units. The computation time of this problem is approximately 70 s. As shown in Table 7, since the MS-DARP-DD has a larger number of required edges than the DARP-DD, more drones can be used to service the required edges in most of the test problems. In addition, the total traveled distance increased in the MS-DARP-DD compared to the DARP-DD due to the increased number of required edges to be served in the graph. When the MS-DARP-DD drone routes are analyzed, it is revealed that the required edges that need to be serviced more than once can be served by the same drones or by different drones. Consequently, multiple services do not have to be performed by the same drone. The URL algorithm [44] was used to analyze the quality of the MS-DARP-DD results obtained by applying the proposed simulated annealing algorithm. Table 8 presents the results achieved using both methods. Table 8 shows that the suggested simulated annealing algorithm outperforms the URL algorithm for all MS-DARP-DD instances.