# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 3 System Model and Problem Formulation
### The \(p\)-Median Optimization Problem  
We use the quadratic integer programming formulation based on the very first model proposed by [PERSON] (2016), which has been extensively applied to solve small to large instances of \(p\)-hub median problems. Hence, before we apply it to the UAV-assisted communications infrastructure optimization problem, we first describe its general formulation according to the key variables, cost function, and optimization constraints.  
The classical \(p\)-hub median problem consists of locating \(p\) hubs from a set of \(n\) nodes in such a way that the average distance between hubs and nodes is minimized. Thus, it is assumed that there is a set \(N\) of graph nodes, with cardinality \(|N|=n\), which are respectively associated with two-dimensional (2D) coordinates \((x,y)\), previously known. For every pair of users \(i\) and \(j\), let \(W_{ij}\) represent \"flow units\" that need to be transferred from a source node \(i\) to a destination node \(j\) across either _one_ or _two_ hubs only. The cost of collecting \(W_{ij}\) units of flow from a source node \(i\) to a destination node \(j\) is denoted by \(T_{ij}\). Given that we want to investigate whether a node \(i\) must (\(i\)) become one of the \(p\) hubs or (\(ii\)) be assigned (or not) to a given hub \(k\), the decision variable is represented by \(X_{ik}\), which is defined as  
\[X_{ik}=\begin{cases}1,&\text{if user $i$ is assigned to hub $k$}\\ 0,&\text{otherwise.}\end{cases}\]  
The particular case \(X_{kk}=1\) means that user \(k\) has been _converted_ into a hub. This is because the only locations that are searched to place the hubs are the positions of the users themselves. This means that, out of the \(n\) positions available, \(p\) of them will be occupied by a hub (i.e., a user will become a hub). Accordingly, the uncapacitated single allocation \(p\)-hub median problem can be formulated as follows:  
\[\text{Minimize:}\quad\sum_{i,j,k\in N}W_{ij}(T_{ik}X_{ik}+T_{kl}X_{ik}X_{jl}+T _{jl}X_{jl}) \tag{1}\] \[\text{Subject to:}\qquad\qquad\sum_{k=1}^{n}X_{kk}=p,\] (2) \[\sum_{k=1}^{n}X_{ik}=1,\qquad\qquad\qquad\qquad\forall\;i\in N\] (3) \[X_{ik}\leq X_{kk},\qquad\qquad\qquad\qquad\forall\;i,k\in N\] (4) \[X_{ik}\in\{0,1\},\qquad\qquad\qquad\qquad\forall\;i,k\in N \tag{5}\]  
Equation (1) describes the cost function as the total sum transfer and transmission costs from origin user to its associated hub, between hubs, and from the destination hub to the destination user. Equation (2) gives the exact number of \(p\) hubs to be placed in the network. Equation (3) is the single allocation constraint, ensuring that the transmission from any source to user \(i\) and vice-versa, i.e., from user \(i\) to any destination node is only sent through the \(p\)-hub to which the user \(i\) is assigned. Equation (4) guarantees that a user cannot have a direct link to a node unless it is a hub, thus avoiding a direct path between origin and destination users and, finally, Equation (5) states that the decision variable must be binary (0 or 1).  
The aforementioned equations summarize the problem, which is, finding the optimal locations of the \(p\) hubs (a subset of the nodes set), as well as the allocation of the remaining nodes to the hubs. This particular quadratic programming formulation has \(\mathcal{O}(n^{2})\) variables and it is hard to solve due to its non-convexity. Despite the possibility of conversion into a mixed integer linear program, it hasbeen demonstrated that the linearization has \(\mathcal{O}(n^{3})\) variables and constraints, thus restricting the size of problems that may be solved [28; 29].