# Sequential Memetic Algorithm Optimization for Allocation Planning in Hostelry Establishments
## 2 Problem Description
### Maximum Dispersion Problem for Optimizing the Chair Allocation  
The previously defined TLP optimization attains the optimal table distribution over the proposed scenario, which is the objective of the first phase of the proposed sequential optimization. The following phase of this algorithm entails the obtention of the optimal locations of each chair over the previously delimited tables. The Chair Location Problem or CLP seeks to obtain the Cartesian coordinates of each chair over a certain scenario that maximizes interpersonal distancing. Consequently, this optimization problem entails the finding of the optimal subset \(\langle C_{i}\rangle=\langle c_{i},\dots,c_{m}\rangle\) which contains the Cartesian coordinates of the center of the \(m\) distributed chairs, being \(\langle c_{i}\rangle=\langle x_{i},y_{i}\rangle\). This subset, \((C_{i})\), is contained within the set of possible chair locations \((L)\). Consequently, likewise to the Maximum Diversity Problem or MDP, a subset of elements is to be selected from a larger set, seeking to optimize the distancing or diversity among elements [22]. These locations are constrained within the CLE limits, delimited by the prior TLP optimization. The resulting optimization can be described through the following mathematical model:  
\[\text{Maximize}\ Z=\textit{ff}_{\textit{div}}(L) \tag{7}\]  
Subject to:  
\[ \begin{split} x_{CLE_{k1}}\leq x_{i}\leq x_{CLE_{k2}}& \quad\forall x_{i}\in L\\ y_{CLE_{k1}}\leq y_{i}\leq y_{CLE_{k2}}&\quad \forall y_{i}\in L\\ \underset{i\in[1,n-1];j\in[i+1,n]}{\text{argmin}}& K_{ ij}w_{i}w_{j}\geq d_{c}\\ \sum_{i=1}^{n}w_{i}=m& w_{i}=\{0,1\}\end{split}  \tag{8}\]  
where \(K_{i,j}\) represents the diversity between the elements \(i\) and \(j\) and can be described as the Euclidean distance between the location of each element, as represented in the following expression:  
\[K_{i,j}=\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}; \tag{9}\]  
\(x_{i},y_{i}\) and \(x_{j},y_{j}\) are the Cartesian coordinates of the locations of the elements \(i\) and \(j\) in the set \((L)\); \(d_{c}\) is the minimum distance separation between chairs; \(\textit{ff}_{\textit{div}}(L)\) represents the fitness function for the evaluation of the diversity (i.e., distance) distribution; \(x_{CLE_{k1}}\leq x_{CLE_{k2}}\) and \(y_{CLE_{k1}},y_{CLE_{k2}}\) are the lower and upper CLE limits for the Cartesian coordinates of the table \(k\), delimited by the previous TLP optimization; \(w_{i}\) is a binary variable that indicates whether a certain location in \((L)\) has been selected as a chair location; \(n\) is the number of locations contained in \((L)\) and \(m\) represents the number of chairs to be distributed. Additional restrictions, such as the invalid placement of chairs in scenario obstacles or the imposition of a minimum distancing among chairs, are not required for the CLP optimization. By delimiting the set of possible locations within the CLE of each table, whose locations have been optimized according to the TLP restrictions, these conditions are now satisfied. Nevertheless, the result of the distance distributions achieved by the optimizations depends on the diversity evaluation, stated as \(\textit{ff}_{\textit{div}}\). Different methodologies are pursued throughout the literature for evaluating the diversity in the MDP; however, the most extended optimization techniques rely on the maximization of the mean diversity (i.e., max-mean) [23], the maximization of the minimum diversity (i.e., max-min) [24], and the maximization of the sum of diversities (max-sum) [25]. These diversity evaluations can be implemented into the CLP by declaring the distance between chairs as the diversity among these two elements, resulting in the following expressions:  
\[\textit{ff}_{\textit{div}}(L)=\left\{ \begin{array}{l}\sum_{i=1}^{n-1}\sum_{j =i+1}^{n}K_{ij}w_{i}w_{j}\\ \frac{1}{n^{2}-n}\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}K_{ij}w_{i}w_{j}\\ \underset{i\in[1,n-1];j\in[i+1,n]}{\text{argmin}}& K_{ij}w_{i}w_{j}\\ \end{array} \right.