# Sequential Memetic Algorithm Optimization for Allocation Planning in Hostelry Establishments
## 1 Introduction  
Organizing and planning a table and chair disposition for accommodating customers is a significant challenge for many hostelry establishments. Multipurpose establishments with a high capacity may redraft their table disposition multiple times a day to optimize the capacity of the establishment [1]. Furthermore, the complexity of devising certain table and chair dispositions scales drastically when incrementing the number of customers. Furthermore, the addition of constraints in the form of obstacles and irregular geometries makes solving the problem even more difficult [2]. The enforcement of a minimum interpersonal separation for reducing the contagion probability due to the COVID-19 pandemic [3] has significantly impacted hostelry establishments [4]. The implementation of these restrictions entails a drastic reduction in the overall customer capacity [5], thus escalating the importance of an optimized table and chair disposition for increasing the received income. One common way to arrange tables in order to optimize the establishment capacity is to select an efficient distribution pattern and scale it to the whole scenario. Triangular and square patterns of sides equal to the minimum interpersonal distance have been widely deployed. These geometric patterns serve as a feasible solution due to their manageable deployment and escalation while also keeping a certain organized distribution [6]. However, these pattern distributions are not necessarily the best solution for every scenario of application. While the triangular shape achieves the highest distancing efficiency, each vertex being separated at the same interpersonal distance among all other vertices,the resulting efficiency of a scaled triangular distribution may be compromised by additional constraints. Unfavorable form factors of the available space, irregular geometries, as well as the presence of obstacles such as columns, furniture, or decorations may limit the utilization of the available space, thus reducing the number of allocated chairs or the actual distancing [7]. Therefore, the search for the optimal chair distribution should not be biased by imposing any given geometrical pattern. However, without the constraints of a regular geometric pattern, the social distancing problem escalates in complexity. The optimal position of each table or chair depends not only on the scenario properties and obstacles, but also on the position of all adjacent tables or chairs. Consequently, although it is possible to derive the optimal position of a given chair, this improvement is based on the premise of a previously fixed table distribution. Therefore, in order to achieve the optimal table distribution, we must analyze the different combinations of table locations. The resulting combinatorial problem raises the number of possible solutions substantially, especially when facing a significant number of tables or chairs to allocate in an intensely discretized space. Problems where multiple elements are to be located over a given scenario to satisfy certain conditions are quite common throughout the literature. Optimizing a wind farm layout [8], finding the optimal sensor distribution for localization architectures [9], efficiently allocating markets for product diversity [10], or distributing facilities over a country [11] are examples of similar combinatorial problems. These optimization problems are built upon the Maximum Diversity Problem (MDP) foundation, which aims to distribute a series of elements over a given scenario while maximizing the diversity among elements [12]. The base MDP has been categorized as NP-Hard [13] due to the number of possible solutions. NP-Hard problems are typically considered challenging to solve efficiently, as there is no guarantee of finding a solution quickly as the problem size increases. Thus, the previously defined problems, which include additional interactions of other elements present in the optimization, further challenge the convergence to the optimal solution.