# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 4 The Biased Randomized and Iterated Local Search (BR-ILS) Algorithm
Firstly, the given number \(p\) of UAVs among the positioned users are randomly chosen, using a uniform probability distribution. Let \(k\) be a candidate location for an UAV and that any user \(i\) could be assigned to \(k\). Thus, all of the data transmitted from user \(i\) to user \(j\) (and vice-versa) has to be sent through UAV \(k\). Accordingly, the inverse of the capacity is computed, i.e., \(T_{ik}=1/C_{ik}\). Moreover, if user \(j\) is assigned to an UAV \(l\), then the inverse of the capacity between these UAVs, \(T_{kl}\), is also computed. In order to evaluate the location \(k\) as a potential placement of an UAV, we calculate \(T_{ik}\) for every positioned user \(i\) in the graph, leading to a matrix whose entries are the elements \(T_{ik}\). Subsequently, for each user in the graph, we add the previously selected UAVs in a list that is sorted according to \(T_{ik}\). Subsequently, the BR technique is applied. In order to better illustrate how the BR works, let us compare it to the greedy randomized adaptive search procedure (GRASP) [38]. In such approach, the best element to be chosen at each stage is put into a restricted candidate list, and the element to be included in the solution is randomly selected using a uniform distribution. Contrary to GRASP, when applying BR, all of the elements are eligible to be selected at each step in the construction of a solution. Thus, at each iteration, the possible UAV candidates are taken into account. Once the initial solution has been generated, the ILS main loop starts. Inside the loop, the current solution is perturbed in order to improve the users' allocations obtained so far, thus generating a new solution. The perturbation occurs by removing a percentage \(per\) of the selected UAVs from the current solution. Once a percentage of the UAVs has been removed, the removed ones are replaced by newly selected UAVs; thus, the solution is reconstructed in order to generate a promising solution during this stage. In order to do that, we generate a new assignment of users to UAVs searching into the neighborhood of the current solution. Subsequently, a local search process is carried out. By following the steps in the local search procedure, the solution approaches the closest local optima by using a neighborhood search scheme. The local search tries to improve the solution at each iteration. Thus, the procedure tries to alternate the selected UAV \(k\) with one of the remaining UAVs in the new solution at hands. Once the promising solution is generated, the cost of the solution containing the new UAV configuration is compared to the solution that contains the original UAV. Moreover, the new configuration is chosen following a credit-based system that allows for accepting a new solution, even if this offers a risk, in comparison to the solution at hands. Here, the credit is calculated as the value of the improvement obtained. Thus, the credit value can be seen as an acceptance criterion. If the promising solution improves the current solution, then the current solution is updated. Subsequently, if the promising solution also improves the best solution found so far, it is updated as well. Notice that, in this step, the total (sum) link capacity is calculated, which takes into account the links from the \(n\) users allocated to the \(p\) UAVs and the links between UAVs. At any time, the best solution found is updated and saved. The loop is executed until the time-based stopping criterion is reached. In the end, the algorithm returns the best solution. All in all, the BR-ILS is a simple and easy-to-implement procedure. As for the complexity of BR-ILS, the time spent is bounded by the predefined time limit \(maxTime\). Within the while loop (line 3 of Algorithm 1), the perturbate function consists in removing a random set of UAVs and selecting another random set, this can be executed in \(\mathcal{O}(n\cdot p\log p)\). The localSearch function consists in changing the assigned UAV of each user and has a complexity of \(\mathcal{O}(n\cdot p)\).