# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 5 Experimental Study
However, due to restrictions that are imposed by the limited memory and CPU clock, it was necessary to manually turn off the aggregator, clique generator, the heuristic, and to set the optimizer time limit to CPXPARAM_TimeLimit = 10,000 s. With these settings, CPLEX is capable of finding optimal solutions as long as a sufficiently large timeframe is provided; otherwise, it will provide a near-optimal solution. Finally, since the branch-and-cut method is deterministic, it is executed only once per instance. The table is organized as follows: (_i_) The first three columns show the size of the instances classified as Small and Large, the number of users represented with \(n\), and the number \(p\) of UAVs to be selected; (_ii_) The next two columns, denoted by Cost (1) and Time give the solution found by the solver CPLEX, and the time it took to find it; (_iii_) The last three columns, denoted by Cost (2), SD, Time, and Gap, give the average cost of the found solutions, the standard deviation, the average run-time, and the corresponding percentage deviation (gap) with respect to the Cost (1) when applying our proposed BR-ILS metaheuristic for the aforementioned sets of generated instances. The elapsed times are shown in seconds. Notice that, for instances that are larger than 50 users and three UAVs, the results obtained by CPLEX were not included, because the solver was not able to find a feasible solution, due to time and memory requirements. In particular, for the instance with 40 users and 3 UAVs, CPLEX finds a worse solution than the one found by BR-ILS, in a much longer time. This situation indicates that the 10,000 s timeframe allowed CPLEX to find a feasible solution, although non-optimal. Furthermore, because BR-ILS is a non-deterministic metaheuristic, it is important to note that the aforementioned results are stable, i.e., present low variability. This is indicated by the zero SD of the Cost observed for all instances, except for the \(n=200,\ p=10\) case which, however, also presents a relatively low level of variation, i.e., just 0.34 over an average cost of 2847.7467. Thus, the results indicate a good level of stability for the method, obtaining almost identical solutions for all instances and runs. All in all, the results that are shown in Table 2 can be considered to be satisfactory, because, for most of the instances, the standard deviation as well as the computation times indicate the capacity of the BR-ILS algorithm to obtain good quality solutions in a few seconds. For illustration purposes, Figure 2 displays the configuration of the network when the algorithm is applied for solving the instance with \(n=20\) and \(p=3\). Figure 2 displays the distribution of users in the area without allocating the UAVs. Figure 2 illustrates the positions of users selected as UAVs, \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multicolumn{2}{c}{**Instance**} & \multicolumn{4}{c}{**CPLEX**} & \multicolumn{4}{c}{**BR-ILS**} \\ \hline  & \(n\) & \(p\) & _Cost (1)_ & _Time (s)_ & _Cost (2)_ & _SD_ & _Time (s)_ & _Gap \%_ \\ \hline \multirow{4}{*}{_Small_} & 10 & & 9.4373 & 180.50 & 9.4373 & 0.00 & 0.12 & 0.00 \\  & 20 & & 33.6638 & 907.34 & 33.6638 & 0.00 & 0.27 & 0.00 \\  & 30 & 3 & 70.4836 & 7204.41 & 70.4836 & 0.00 & 0.45 & 0.00 \\  & 40 & & 134.3173 & 7202.50 & 120.0516 & 0.00 & 0.70 & \(-\)10.72 \\  & 50 & & – & – & 179.2856 & 0.00 & 0.81 & – \\ \hline \multirow{4}{*}{_Large_} & 100 & & – & – & 773.9002 & 0.00 & 116.09 & – \\  & 200 & 10 & – & – & 2847.7467 & 0.34 & 476.30 & – \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of the results that were obtained with CPLEX and BR-ILS. as well as the assignments that were provided by the solution. Once our methodology is applied, the algorithm is able to find the best placement of UAVs, and the set of users assigned to the selected UAVs. The UAVs are represented with a squared symbol.