Sequential Memetic Algorithm Optimization for Allocation Planning in Hostelry Establishments

Abstract

Hostelry establishments face the challenge of devising a table and chair allocation for accommodating their customers on a daily basis. This problem scales significantly with the introduction of constraints, such as scenario obstacles or the requirement of a minimum distance separation. The TLP (Table Location Problem) and the CLP (Chair Location Problem) are NP-Hard complexity problems that aim to attain the optimal table and chair distribution for certain applications. Existing approaches to this problem fail to address both the TLP and CLP simultaneously, thus resulting in suboptimal solutions achieved by imposing optimization constraints. Therefore, in this paper, a sequential optimization methodology based on a GBLS MA (Gradient-Based Local Search Memetic Algorithm) optimizations is proposed for optimizing the table and chair disposition simultaneously while also considering scenario and distancing restrictions. The proposed methodology is then implemented into a realistic establishment, where different optimization strategies within the CLP are compared. Results prove the viability and flexibility of the proposed sequential optimization for complex hostelry scenarios.

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. Such is the case of the chair or table distribution optimization problem.

Due to the high complexity of these problems, a direct approach that analyzes each possible solution is unfeasible, so multiple metaheuristic techniques have been implemented for these optimization problems [14].

In our previous works, a Genetic Algorithm (GA) was proposed for optimizing the student distribution in schools during the COVID-19 pandemic [15]. This optimization problem, described as the Table Location Problem (TLP), seeks to obtain the optimal distribution of a given number of tables over a specific scenario that guarantees the minimum distance separation and maximizes the mean interpersonal distance while also taking into consideration the scenario properties. The algorithm located a given number of tables within the scenario limits in an optimized distribution for the scenario geometry, while also respecting the scenario obstacles.

Later on, we designed a Memetic Algorithm (MA) for escalating the TLP to hostelry applications [16]. In these scenarios, the space of solutions increases significantly due to the consideration that a variable number of people may be allocated in each table. The proposed MA was further enhanced with the introduction of memory chains for recalling each individual potential for improvement in [17], improving the overall exploration and exploitation of the available space, resulting in an overall better performance.

However, our previous approach dissociated the table and chair allocation problem. This decision was selected based on the regular operation of a common hostelry establishment, where each table may accommodate a variable and unknown number of customers [18]. Nevertheless, certain establishments where celebrations or events are held and the number of assistants is known may prefer optimizing the chair and table distribution for allocating a higher number of customers or obtaining a more distanced disposition [19].

The table and chair allocation problem has never been attained simultaneously in an unbounded optimization. Luis Bañón et al. [7] analyze different table and chair distribution patterns for different scenario geometries. This provides an efficient approach to the problem; however, the performance of these distributions is compromised for scenarios with a high obstacle density, thus representing a suboptimal approach that does not completely exploit the whole space of solution, resulting in potential empty space being unexploited.

Martina Fischetti et al. [20] apply metaheuristic techniques for optimally allocating tables in hostelry scenarios; nevertheless, this study only focused on locating the tables without analyzing varying seating positions or the presence of obstacle regions. Therefore, this work provides an incomplete solution to the CLP, as the chair arrangement is not taken into consideration when deploying the tables.

On the contrary, Hassan Ugail et al. [6] implemented a heuristic-based algorithm for optimally distributing a certain number of chairs over a given scenario, considering different constraints and obstacles. However, while tables of varying geometry are taken into consideration for the optimization, these table positions are defined as fixed constraints, prior to the optimization, which limits the number of possible solutions as well as the distance distribution optimization potential.

Therefore, in this paper, a combined optimization of the table and chair distribution is proposed for hostelry applications. The exploration of the space of solutions growth introduced by establishing variable table positions may disclose solutions that further optimize the distance distribution, whereas the previously defined constrained optimizations are unable to achieve such solutions.

However, the combination of two NP-Hard problems, such as the table and chair distribution, may result in a computational cost unacceptable for daily operations in certain establishments. Consequently, following the definition of the seat environment for each table in [16], a sequential optimization algorithm that first distributes the tables according to their seat location environment and then allocates the chairs may achieve improved solutions to the constrained problem while also significantly reducing the computational cost.

Furthermore, this optimization is performed by a sequential MA optimization with memory chains for improving the optimization performance of both phases of the algorithm. Multiple genetic operators and fitness optimization functions are specifically devised for this problem in order to attain the best solution. The proposed algorithm is later proved in a realistic scenario based on the Guadi Casa Botines, an establishment designed for celebrations located in the city of León, Spain.

The obtained results confirm the soundness of the proposed methodology, obtaining near-optimal chair and table distributions for both the interpersonal distance and for the hostelry establishment arrangement strategy.

The remainder of this paper is organized as follows: the description of the table location problem and the subsequent chair location problem are described hereafter in Section 2, Section 3 details the proposed methodology and the MA structure, the optimization results over the selected scenario are presented in Section 4, while Section 5 concludes this paper.

2. Problem Description

2.1. Table Location Problem in Hostelry Applications

To achieve optimal space utilization in the competitive world of hostelry, it is essential to address the Table Location Problem (TLP) as a foundational step. The proposed methodology for attaining optimal space utilization in hostelry applications requires addressing the TLP in the first place. The TLP looks to find the Cartesian coordinates of the center of gravity of each of the tables deployed in a particular scenario, both for achieving the maximization of the distance among the tables and for introducing the maximum number of tables in safety conditions in the application scenario.

This entails the finding of the optimal subset $(\langle T_i\rangle =\langle t_i,\dots ,t_n\rangle )$ containing the Cartesian coordinates of the center of gravity of the n tables deployed $(\langle t_i\rangle =\langle x_i,y_i\rangle )$, within the set of available locations for each table within the scenario of application $\left(T\right)$.

This problem, exponential in complexity [17], looks to maximize the distance among the tables while achieving uniformity with these distances. In this sense, the Cartesian coordinates of the tables are modified during the optimization (i.e., the decision variables of the problem) also fulfilling some restrictions for ensuring the achievement of valid table dispositions. This states the following mathematical model for the TLP:

$$\mathrm{Maximize}Z=\mathit{f}\mathit{f}(\mathit{f}{\mathit{f}}_d\left(T_i\right),\mathit{f}{\mathit{f}}_{\mathit{pen}}\left(T_i\right))$$

(1)

Subject to

$$\begin{array}{cc}\hfill x_{l_1}\le x_i\le x_{l_2}& \forall x_i\in t_i;t_i\in T_i;t_i\notin U\hfill \\ \hfill y_{l_1}\le y_i\le y_{l_2}& \forall y_i\in t_i;t_i\in T_i;t_i\notin U\hfill \\ \hfill d_{i{j}_{\mathit{CLE}}}\ge d_s& \forall i,j\in 1,\dots ,n;i\ne j\hfill \\ \hfill d_{k{i}_{\mathit{CLE}}}\ge d_w& \forall 1,\dots ,n;\forall k\in 1,\dots ,n_{\mathit{obs}}\hfill \end{array}$$

(2)

where $\mathit{f}{\mathit{f}}_d$ and $\mathit{f}{\mathit{f}}_{\mathit{pen}}$ are fitness functions for maximizing the distance among the tables and for guiding the optimizations to valid table distributions, respectively, $x_{l_1},x_{l_2},y_{l_1}$, and $y_{l_2}$ are the scenario limits for the Cartesian coordinates of the center of gravity of the tables; U is the subset including the forbidden location for the tables due to the obstacles of the scenario; $d_{i{j}_{\mathit{CLE}}}$ represents the distance among the Chair Location Environment (CLE) of the tables i and j, which must exceed the security distance $\left(d_s\right)$ of 1.5 m set in the Spanish legislation during the pandemic [21]; $n_{\mathit{obs}}$ is the number of obstacles defined in the scenario and $d_{k{i}_{\mathit{CLE}}}$ is the distance from the obstacle k to the closest point in the CLE of the table i which must allow the passage of the waiters for a proper service exceeding a threshold distance $\left(d_w\right)$.

An important fact to highlight in this model is the calculation of the distance between the CLE of different tables. The CLE is defined as the region around each table where chairs may be placed. By defining a bounded region around each table for the chair allocation, the TLP optimization is carried out independently of the Chair Location Problem CLP, described in the next subsection, while also considering the interpersonal distancing between variable chair locations in the distance calculation.

To achieve this objective, the distancing between tables is deduced from the separation between the two CLE regions of those tables, as depicted in Figure 1. From this scheme, we can compute the distance between potentially seated individuals in a stage in which the number and location of the chairs are unknown. This procedure, shown in Figure 1, guarantees the specified minimum distance separation between any pair of chairs from different tables, as described in [16].

The fitness functions for the optimizations look for reaching equilibrated table dispositions in which the mean distance among the tables is maximized, while also pursuing a certain uniformity in the distance distribution. This leads to the following formulation of the main fitness function of the optimization:

$$\mathit{f}{\mathit{f}}_d\left(T_i\right)={\displaystyle \frac{1}{n}}\sum _{i=1}^n{J}_i-{\displaystyle \frac{\epsilon }{n}}\sqrt{\sum _{i=1}^n{\left(J_i-{\mu }_{\mathit{closest}}\right)}^2}$$

(3)

where

$$J_i=\underset{j\in [1,n];i\ne j}{\mathrm{argmin}}\left({\mathit{d}}_{{\mathit{i}}_{\mathit{CLE}}}\right);$$

(4)

${\mathit{d}}_{{\mathit{i}}_{\mathit{CLE}}}$ is the vector containing the distances from table i to the other tables of the disposition, $\epsilon$ is a hyperparameter weighting the importance of reaching equilibrated table dispositions, and ${\mu }_{\mathit{closest}}$ is the mean value of the distance among the closest tables of the table disposition analyzed.

In addition, some restrictions for attaining valid table dispositions must be considered through a negative penalization fitness function, as follows:

$$\begin{array}{ccc}\hfill \mathit{f}{\mathit{f}}_{\mathit{pen}}\left(T_i\right)& =& -(\mathit{f}{\mathit{f}}_s+\mathit{f}{\mathit{f}}_w+\mathit{f}{\mathit{f}}_{\mathit{obs}})\hfill \\ \hfill \mathit{f}{\mathit{f}}_s& =& \sum _{i=1}^n\mathit{f}{\mathit{f}}_{s_i}\hfill \\ \hfill \mathit{f}{\mathit{f}}_{s_i}& =& \left\{\begin{array}{cc}{\left(J_i-d_s\right)}^2& \mathrm{if}{J}_i<d_s\\ 0& \mathrm{otherwise}\end{array}\right.\hfill \\ \hfill \mathit{f}{\mathit{f}}_w& =& \sum _{i=1}^n\mathit{f}{\mathit{f}}_{w_i}\hfill \\ \hfill \mathit{f}{\mathit{f}}_{w_i}& =& \left\{\begin{array}{cc}{(R_i-d_w)}^2& \mathrm{if}{R}_i<d_w\\ 0& \mathrm{otherwise}\end{array}\right.\hfill \\ \hfill \mathit{f}{\mathit{f}}_{\mathit{obs}}& =& Z\Theta \hfill \end{array}$$

(5)

where

$$R_i=\underset{k\in [1,n_{\mathit{obs}}]\cup {\mathit{\pi }}_{\mathit{w}}}{\mathrm{argmin}}\left({\mathit{d}}_{\mathit{k}\mathit{i}}\right);$$

(6)

$\mathit{f}{\mathit{f}}_s$, $\mathit{f}{\mathit{f}}_w$, and $\mathit{f}{\mathit{f}}_{\mathit{obs}}$ represent the fitness functions for considering the achievement of the security distance among the CLE zones of each table, the facility for serving for the waiters and the avoidance of the location of a table in a forbidden region, respectively; ${\mathit{d}}_{\mathit{k}\mathit{i}}$ is the vector containing the distance from table i to each of the obstacles and the walls of the scenario, contained in the vector ${\mathit{\pi }}_{\mathit{w}}$; $\Theta$ is the number of tables located in forbidden regions in a particular disposition and P a weighting hyperparameter for giving enough importance to this factor.

2.2. 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, $\left(C_i\right)$, is contained within the set of possible chair locations $\left(L\right)$.

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:

$$\mathrm{Maximize}Z=\mathit{f}{\mathit{f}}_{\mathit{div}}\left(L\right)$$

(7)

Subject to:

$$\begin{array}{c}{x}_{{\mathit{CLE}}_{k1}}\le x_i\le x_{{\mathit{CLE}}_{k2}}\forall x_i\in L\\ y_{{\mathit{CLE}}_{k1}}\le y_i\le y_{{\mathit{CLE}}_{k2}}\forall y_i\in L\\ \underset{i\in [1,n-1];j\in [i+1,n]}{\mathrm{argmin}}{K}_{ij}{w}_i{w}_j\ge d_c\\ {\displaystyle \sum _{i=1}^n}{w}_i=m{w}_i=\{0,1\}\end{array}$$

(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};$$

(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 $\left(L\right)$; $d_c$ is the minimum distance separation between chairs; $\mathit{f}{\mathit{f}}_{\mathit{div}}\left(L\right)$ represents the fitness function for the evaluation of the diversity (i.e., distance) distribution; $x_{{\mathit{CLE}}_{k1}}\le x_{{\mathit{CLE}}_{k2}}$ and $y_{{\mathit{CLE}}_{k1}},y_{{\mathit{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 $\left(L\right)$ has been selected as a chair location; n is the number of locations contained in $\left(L\right)$ 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 $\mathit{f}{\mathit{f}}_{\mathit{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:

$$\mathit{f}{\mathit{f}}_{\mathit{div}}\left(L\right)=\left\{\begin{array}{c}{\displaystyle \sum _{i=1}^{n-1}\sum _{j=i+1}^n{K}_{ij}{w}_i{w}_j}\hfill \\ {\displaystyle \frac{1}{n^2-n}\sum _{i=1}^{n-1}\sum _{j=i+1}^n{K}_{ij}{w}_i{w}_j}\hfill \\ {\displaystyle \underset{i\in [1,n-1];j\in [i+1,n]}{\mathrm{argmin}}{K}_{ij}{w}_i{w}_j}\hfill \end{array}\right.$$

(10)

Through the maximization of these functions (i.e., max-sum, mean-max, and max-min), the CLP may achieve a distance distribution that satisfies the restrictions expressed in Equation (8).

3. Sequential Optimization

To effectively tackle the challenges posed by the CLP and the TLP, it is important to recognize their underlying complexity. Given that the Multi-Dimensional Problem (MDP) is classified as NP-Hard [26], it follows that related problems like the CLP and TLP, which are based on the foundations of the MDP, also share this complexity classification. Consequently, the implementation of metaheuristic techniques, such as GA and MA, is proposed to achieve optimal solutions within a polynomial time frame.

However, the combinatorial explosion derived from the combined complexity of simultaneous optimization of the TLP and the CLP threatens the convergence to an acceptable solution. Therefore, in this paper, a sequential optimization methodology is proposed, as depicted in Figure 2. The sequential optimization is divided in two separate stages or phases, the first stage optimizes the TLP through an LS MA optimization based on the establishment scenario $\pi$. The second stage takes as input the scenario with the optimally distributed tables ${\pi }^{\prime }$ by the previous stage, resulting in the desired chair and table distribution.

Despite the fact that the separate optimization of the TLP and CLP may reduce the space of solutions, limiting the optimal solution achieved, the definition of the CLE within the TLP introduces a greater degree of information regarding the posterior chair location optimization. Consequently, in the TLP optimization phase of the algorithm, the chair locations, although yet undetermined, are considered in the optimization, guiding the TLP optimization into a table distribution favorable for the CLP optimization.

Therefore, the proposed sequential optimization results in a compromise solution between computational complexity and achievable quality of the solution, attaining greater distance distributions than purely table distribution optimizations without the associated complexity of unrestricted CLP or a combined CLP and TLP optimization.

The resulting methodology, shown in Figure 2, is composed of two principal stages. The first phase, composed of an MA optimization of the TLP, results in a table distribution that maximizes the distancing between tables regarding the CLE. The second phase operates within the CLE of the previously fixed tables, obtaining the optimal chair distribution through an MA optimization.

MAs are optimization algorithms that integrate into GA optimization a certain knowledge of the problem, conceptualized as “meme”, for improving the performance of the optimization [27]. This knowledge is introduced into the optimization through a Local Search (LS), built specifically for each problem for improving the initial convergence of the algorithm, avoiding local maximums, and obtaining overall superior solutions [28]. MAs have been implemented widely for optimization paradigms, especially for solving NP-Hard problems [29].

MAs rely on the GA optimization foundations for attaining the desired solution. GAs implement evolutionary strategies for guiding optimization into the optimal solution. Within these algorithms, a population of individuals is modeled, where each individual carries the decision variables of the optimization problem, each individual representing a certain solution for the problem [30].

Throughout multiple generations, the generated population of the MA is evaluated based on its adaptation to the problem characteristics. The received values play a key role in the following genetic operators, shown in Algorithm 1, whose purpose is to guide the population into the optimal solution.

Algorithm 1: MA Structure for the TLP and the CLP Optimizations

This pseudocode describes the basic structure of the followed local search MA optimization for the CLP and the TLP optimizations. The algorithm commences by loading the scenario of optimization and initializing the population and memory chains. The memory chains store certain information relative to the potential improvement of each individual for the LS.

The mentioned populations are then evaluated according to the fitness function of each particular problem; once assigned a fitness value to every individual, the population is exposed to a series of genetic operators (i.e., Elitism, Selection, Crossover, and Mutation) which introduce selection pressure and diversity into the optimization, critical for the optimization performance [31]. The LS is then applied to a selection of the best-suited individual. This selection is performed on a collection of the best-adapted and random individuals. The selection criteria evaluate the memory chains of each individual, selecting those that exhibit a greater potential improvement for the local search [32].

Once the selection is concluded, the local search is performed within the chosen individuals with the objective of improving the initial distributions. After the resolution of the LS, the newly acquired fitness value is compared to the initial value, prior to the LS, any fitness improvement results in the replacement of the initial individual obtained throughout the LS.

Nevertheless, Algorithm 1 reflects the basic structure from which the TLP and CLP MA optimizations are designed. From this scheme, each problem is characterized by the codification of the individuals and the specific design of certain algorithms within the MA, such as the fitness function or the local search, which are described in this section.

3.1. Table Distribution Optimization

The first stage of the algorithm consists of the MA optimization for optimally allocating a certain number of tables over the introduced scenario. The algorithm’s basic structure is described in the Algorithm 1. Once loaded, the base scenario $\pi$, with the boundaries and obstacles, the population is generated according to the proposed codification, depicted in Figure 3.

Each individual contains the Cartesian coordinates of each table over the given scenario. These values are coded in binary, which is a key design factor for future genetic operators of the MA. A binary to decimal scaled conversion is proposed for optimally surveying the given scenario, avoiding the location of tables outside the scenario boundaries in irregular establishments as proposed in [15]. Moreover, each table carries an ID tag for its identification during the LS and for the CLP optimization.

The conversion and scale of each table location to the scenario of application and the obstacle collision detection are performed within the fitness function, evaluating each individual according to the achieved distance distribution and the fulfillment of certain restrictions. The main structure of this algorithm is described in Algorithm 2.

Algorithm 2: Fitness function for the TLP MA ($d_{CLE},\mathit{Population},\pi$)

The fitness evaluation of each individual starts by obtaining the Cartesian coordinates of each table location, T. From these locations, the interpersonal distance distribution between tables d is computed, which is measured as the Euclidean distance between the CLE regions of each table, as shown in Figure 1.

Therefore, the distance calculation requires the obtention of the distance from each table center to the intersection of each CLE region for the intersection angle. However, this distance, $d_{CLE}$, is only dependent on the angle of intersection $\alpha$ between tables and the table geometry.

Consequently, in the proposed algorithm, a $d_{CLE}$ polar distribution is computed at the start of the TLP optimization for multiple intersection angles, saving these values for the table-to-table distance calculation, reducing the complexity of the fitness evaluation algorithm [16].

Moreover, the algorithm evaluates the number of collisions with obstacles and the number of distances that do not reach the $d_s$ minimum interpersonal distance. The severity of the infringement ${\delta }_{d_s}$ is also measured for the unsuitable distance, where ${\delta }_{d_s}=d_s-d_{i,j}$. Based on this restriction analysis, two different evaluation methodologies are proposed.

Table distributions that exhibit any penalization (i.e., obstacle collision or distance infraction) are penalized according to the expressions exhibited in Equations (5) and (6), resulting in a negative fitness value. On the other hand, table distributions that do not result in any obstacle collision or any distance infraction result in a positive fitness function, guiding the optimization into adhering to these imposed restrictions.

Once evaluated, the individuals are preserved, arranged, crossed, and mutated through the respective genetic operators. The cycle of the fitness evaluation and these operators constitute the basic GA optimization, which is complemented in this paper with a specifically designed local search for the TLP, which takes place when certain criteria (i.e., probabilistic, or sequential activation) are met, thus resulting in the proposed LS MA.

The proposed local search aims to intensify a reduced sample of individuals from the population set, improving the fitness value of these individuals through a GBLS (Gradient-Based Local Search) procedure [33], thus guiding the optimization into achieving the desired solution.

The selection of the local search individuals is performed over a certain pool of individuals from the base population that consists of a combination of the best-adapted individuals and random selections, thus attaining a diverse and elitist sample of the population [34]. From this initial pool, the local search individuals are selected by analyzing the improvement potential of each drafted individual. The improvement potential of each table distribution is measured by the intensity parameter, described through the following expression:

$$I_i=C_1\delta +C_2\mu +C_3{n}^{-1}$$

(11)

where $I_i$ represents the intensity of the individual i; $C_1,C_2$, and $C_3$ are co-factors obtained experimentally, as stated in [35]; $\delta ,n$ and m are contained within the memory chains of each individual and represent, respectively, the fitness improvement of the last LS, the number of times that the individual have been improved, and the improvement viability, measured as

$$\mu =\rho \sum m_j;$$

(12)

where $\rho$ is the table-moving step and $m_j$ the number of table movements performed within the LS execution j.

The memory chains are initialized in default values (i.e., null $\delta ,n,\rho ,m$) at the start of the optimization and are then updated within the LS procedure. Individuals that undergo any alteration in the mutation operator have their memory chains reinitialized; the same procedure is applied to the novel individuals generated in the crossover function. However, preserved individuals in the proposed methodology conserve their memory chains, thus enhancing the LS individual’s selection.

Once the individuals have been selected, the GBLS is performed for each of the local search individuals, intensifying the respective table distributions through the methodology described in Figure 4.

The purpose of the GBLS for the TLP is to improve the table distribution by introducing multiple small movements in certain table positions. Each movement is performed based on a step size $\rho$ and a movement direction. The obtention of the optimal movement direction for each chair constitutes a significant challenge, the presence of obstacles, the minimum distance restriction, and the exceeding number of possible configurations of distributions threaten the viability of any exact procedure [16].

Therefore, an iterative approach is proposed where the direction of movement is computed locally for a single table through the distance gradient of the utmost proximate table:

$$\nabla d_{i,j}=\left({\displaystyle \frac{x_i-x_j}{K_{i,j}}},{\displaystyle \frac{y_i-y_j}{K_{i,j}}}\right)$$

(13)

where $\nabla d_{i,j}$ obtains the gradient direction from table j to table i.

The resulting direction of movement increases the minimum distance separation of the moved table i until the minimum distance is measured to another adjacent table k, different from j. Following Figure 4, the iterative algorithm will evaluate the gradient with table k, increasing the minimum distance until a certain number of movements are performed or until the result position is repeated from previous steps.

Moreover, the GBLS also aims to assist the table distribution in evading obstacles. When the moving table i is located within an obstacle, the algorithm computes the gradient for obtaining the direction that distances the table from the obstacle until the table evades the obstacle.

Nevertheless, the proposed GBLS only intensifies one table per LS iteration, and thus the table selection for each iteration constitutes a cardinal step for improving the individual fitness value. A selection methodology is proposed where the algorithm evaluates multiple parameters that are related to the potential of each table for improving the individual fitness value, which is obtained from the following expression:

$$P_i=C_4{d}_{\mathit{min}}-C_5{N}_{\mathit{adj}}-C_6{N}_{\mathit{rep}}+F_1+X$$

(14)

where $C_4,C_5$, and $C_6$ are co-factors adjusted experimentally; $N_{\mathit{adj}}$ is the number of adjacent tables (i.e., number of tables under a certain radius); $d_{\mathit{min}}$ is the minimum distance among the adjacent tables; $N_{\mathit{rep}}$ is the number of times that the table i has been selected for the given individual; $F_1$ is a step function of value $\kappa$ when the table i is within an obstacle and 0 otherwise, and X is a random variable.

The proposed methodology favors the selection of tables that induce a penalization in the fitness value (i.e., distance or obstacle restriction). On the other hand, the selection penalizes tables that have undergone previous selections as well as tables that have a considerable number of adjacent tables, thus favoring the selection of those tables within the periphery, expanding the limits of the table distributions, exploiting all the available space.

Nevertheless, as previously stated, no methodology is optimal for each possible table configuration, and thus a random variable is implemented to introduce a degree of entropy into the selection procedure, which allows for the exploration of other possibilities that are unreachable within the proposed selection methodology [36].

Consequently, the GBLS is implemented through an iterative intensification of certain tables, where each table is moved at least $n_t$ times for each selection, and $n_s$ selections are performed for each LS individual.

The resulting MA optimization excels in scenarios with a high obstacle density, such as the one proposed in this paper, improving the initial convergence of the optimization and exploiting all the available space, improving the table distribution for the following CLP optimization, discussed hereafter.

3.2. Chair Allocation Optimization

The conclusion of the TLP MA results in the obtention of an optimized table distribution over the approached environment. Once locating the tables, the proposed sequential optimization continues with the chair distribution optimization. The CLP optimization aims to obtain the chair distribution that maximizes the interpersonal distance. The scenario of optimization, ${\pi }^{\prime }$, is composed of the CLE of the previously fixed tables.

Moreover, the NP-Hard complexity of this problem requires the employment of metaheuristic techniques for obtaining a valid solution within a polynomial time [37,38]. Consequently, due to the existing similarities between the TLP and CLP, an LS MA is proposed for obtaining an adequate solution for CLP optimization.

However, the dissimilarities that differentiate the CLP from the TLP, such as the different scenarios, inhibit the direct application of the methodology proposed for the TLP into the CLP. Due to these aspects, an MDP-based codification is proposed for attaining the desired solution, represented in Figure 5.

Within the proposed codification, each individual carries the whole set of possible chair locations. These chair locations are contained within each table CLE. Therefore, the space of possible locations is discontinuous, starting in the CLE of the ${\mathit{Table}}_1$ in Figure 5 covering the table chair location environment counterclockwise, then moving to the CLE of ${\mathit{Table}}_2$ repeating the presented procedure until all tables are covered.

Each table is identified by its ID number, defined in the TLP codification; however, in order to trace a more connected space, the table identifications are rearranged according to their final location after the TLP optimization, covering the scenario from top to bottom and from left to right.

Furthermore, in the proposed codification of the individual genotype, each bit represents whether a location is selected or not as a chair location. Consequently, the sum of each individual genotype must always add up to the number of chairs to be distributed. This supposes a relevant constraint for the crossover and mutation operators, where the genotype of each individual is permutated in different ways for exploring the space of solutions.

The unchecked exercise of these operators may result in changes in the genotype that increase or decrease the total number of ones within each individual, thus altering the associated number of chair placements and resulting in invalid distributions.

Constrained GA optimizations, where genetic operators may result in unfeasible solutions to the proposed problem, are a common problem throughout the literature [39,40]. In order to bypass this situation, three methodologies are usually employed for guiding the convergence into the problem domain [41].

The first solution entails the design of weighted penalties within the fitness evaluation for those unfeasible solutions. However, this approach has unfavorable results for problems with a high probability of generating an unfeasible solution [42]. Furthermore, the weight of each penalization should be revaluated for each different scenario of application, affecting the flexibility of the proposed methodology.

On the contrary, the second approach focuses on the employment of special decoders and repair operators. These algorithms project invalid individuals into the feasible region [43]. However, these operators may result in the loss of genetic diversity when the feasible region is small and discontinuous.

Furthermore, the third approach is centered on the development of domain-specific GA [44]. This methodology is based on the development of specific GA operators that operate within the problem-feasible region. This procedure usually results in the best solution, especially for problems with underrepresented feasible regions, such as the CLP optimization [45].

However, the design of these algorithms is an arduous task, as these methodologies must prove an equal exploration of the whole space of solutions in order to provide the diversity required for solving the problem [46]. Nevertheless, due to the limited and discontinuous feasible region of the MDP codification, the implementation of domain-specific MA is required to attain the desired solution.

Therefore, in this paper, a novel crossover and mutation operator are proposed for attaining a constrained GA optimization of the MDP for the first time in the authors’ knowledge. The proposed crossover operator, detailed in Algorithm 3, aims to provide a sufficient genetic drift without incurring excessive diversification, which could imperil the algorithm’s convergence with the optimal solution.

The proposed algorithm adapts the multiple-point crossover operator into a variable segmentation process for operating within the constant number of restrictions [47]. The algorithm starts by initializing the new population of individuals, defined as offspring, which share the codification of the old population but are initialized with all zeros. For each pair of individuals within the population and the offspring (i.e., the progenitors and descendants), the algorithms trace different segments for reallocating the bits within the fathers to the descendants.

Each segment is determined by its origin point, its length, and its final point. The origin point is determined randomly among each possible bit position that has not been selected or that has been in a previous segment. The length of the segment is calculated through the following equation in order to avoid overflow of the parents’ descendants with their own:

$$L=\mathit{min}\{N-\mathit{max}\{\sum D_1,\sum D_2\},L_0\}$$

(15)

where L is the segment length; N is the number of chairs (i.e., the total number); $D_1$ and $D_2$ represent the two formed descendants from each pair of progenitors, with the binary codification proposed for the CLP and $L_0$ being a hyperparameter for initializing the default length.

Algorithm 3: Pseudocode of the variable segmentation-designed crossover operator for the CLP optimization (Population, Num Chairs).

Once setting the origin point and length of the segment, the end point is deduced from the individual bit positions, as represented in Figure 6.

The segment advances through each individual binary codification in a given direction, each bit representing a unit of length. The segment may surpass previously segmented bits and can link the end and the beginning of the genotype. Once obtaining the segment, similar to the multiple-point crossover, each bit position and value is transferred to the descendants. The bit assignment that determines which progenitor string adheres to each descendant is computed randomly at each segmentation.

The segmentation process is repeated until at least one of the descendants reaches the required number (i.e., the sum of its genotype equals the number of chairs). However, a possible outcome of this procedure is the event in which one descendant still lacks a certain number. A sequential methodology is proposed for completing the last individual, in which the leftover ones in both progenitors are passed to the remaining descendant.

Nevertheless, progenitors that share leftovers within the same positions require additional operations for delivering the required number to the uncompleted descendant. Thus, for each missing one, the algorithm iteratively passes a bit of value from a progenitor to the missing descendant. The progenitor is randomly selected, and the bit position is randomly selected among all possible positions (i.e., all positions where the progenitor has a one and the descendant a zero).

The repetition of this procedure for every pair of individuals from the population constitutes the new generation of individuals, in which each individual has an equal number to the number of placed chairs.

On the other hand, the CLP codification also requires the particularization of the mutation operator. Similarly, to the crossover operator, the permutation of the individual genotypes performed within the mutation algorithm may shift the total number. Consequently, a two-step mutation operator has been proposed for altering certain individuals within the population.

For each mutated individual, the first step entails the mutation of ones, where each bit has a low percentage of being negated, turning into a zero. After the negation step, the algorithm computes the number of ones and permutes random zeros into ones until the total number of ones fits the desired number of chairs.

Once defining the mutation and crossover operators, we can elaborate the fitness function for the proposed LS MA optimization. Multiple fitness functions have been proposed in order to evaluate the diversity (i.e., distancing among individuals) of the chair distribution. Three evaluations are commonly applied to MDP optimization problems for achieving the maximum diversity, as shown in Equation (10) (i.e., max-sum, max-mean, and min-max) [48].

Therefore, in search of the most-suited methodology, all fitness methodologies will be considered for the results section. Nevertheless, for the CLP, both the minimum distance achieved and the mean distancing are important parameters. However, the separation of both metrics into different optimization functions may guide the convergence of the optimization into reaching each separate metric and not both combined [49]. Therefore, a fourth fitness function is proposed for the CLP optimizations, which combines the min-max and max-mean functions for guiding the convergence into reaching a more adequate solution, presented in the following equation:

$$\mathit{f}{\mathit{f}}_{\mathit{mix}}=\mathit{f}{\mathit{f}}_{\mathit{\text{max-mean}}}+M+{(1+\mathit{f}{\mathit{f}}_{\mathit{\text{min-max}}})}^3$$

(16)

where

$$M={\left(1+\overline{D_1}\right)}^b+\sum _{i=1}^3{\left(1+\overline{Q_i}\right)}^{a_i};$$

(17)

$\overline{Q_i}$ represents the averaged distance quartiles of the distance distribution of the analyzed individual; $\overline{D_1}$ is the averaged first decile of the distance distribution, and $a,b$ are hyperparameters for weighting the fitness value.

Based on the achieved fitness value, the selection and elitism operate similarly to the previous TLP optimization. Furthermore, due to the elevated number of possible locations, the initial phase of the optimization of the algorithm proves especially problematic due to the random distribution of chairs over the scenario; thus, multiple consecutive changes are required to improve the mean and minimum distance.

Consequently, a GBLS is proposed for improving the initial convergence of the CLP optimization, improving the initial growth while avoiding local maximums. Similar to the TLP, the proposed LS is applied to a certain number of individuals, selected from among the best-fitted and other random individuals. From this draft, the final selection of the local search individuals is performed based on the intensity parameter described in Equation (11). The improvement viability expressed within this equation has been reformulated for the CLP, resulting in the following expression:

$$\mu =\rho \sum m_j$$

(18)

where $\rho$ represents the movement step and $m_j$ the number of chair movements performed within the LS execution j.

Once selecting the LS individuals, the GBLS takes place for improving the fitness value of the given chair distributions. The proposed methodology for the CLP LS is depicted in Figure 7.

For each individual, the proposed LS performs multiple chair selections for evaluating the chair positions whose movements entail the most fitness improvement potential. This potential is measured by a parameter that evaluates different aspects regarding the chair proximity, resulting in the following expression:

$$P_i=C_7{d}_{\mathit{min}}-C_8{N}_{\mathit{table}}-C_9{N}_{\mathit{rep}}+X$$

(19)

where $C_7,C_8$, and $C_9$ are co-factors adjusted experimentally; $N_{\mathit{table}}$ is the number of placed chairs within the table in which the chair i is located; $N_{\mathit{rep}}$ is the number of times that the chair i has been selected for the analyzed individual; and X is a random variable.

Similar to the potential for selecting tables for the TLP optimization, the CLP selection favors those chairs that present a deficient minimum interpersonal distance, which may severely penalize the fitness value. Nevertheless, a random parameter is also proposed in order to introduce a certain degree of entropy into the optimization, resulting in a well-rounded selection procedure.

Once a chair has been selected, the algorithm intensifies the chair location by evaluating the optimal direction of movement. Following the codification of the individual, the range of movement of a chair within a table is limited to two opposite directions (i.e., clockwise and counterclockwise). Therefore, the GBLSs perform exploration for both directions, moving the selected chair in each direction until the minimum distance between the selected chair and the most proximate chair of a given instance is less than the minimum distance of the previous instance. The algorithm then saves the chair location of the last valid instance.

The result of this procedure is the obtention of the best-suited chair locations for both directions, regarding only the minimum distance. The GBLS then selects the location that attains the minimum distance between (i.e., one of the two directions or the initial position) replacing the original position if modified.

The proposed methodology proves essential for improving the initial phase of the optimization, where multiple chairs are scattered around the environment, and where the fitness evaluation may be compromised by the resulting distance distribution, especially for the min-max strategy.

In conclusion, the previously detailed sequential optimization composed of two LS MA optimizations proves mandatory for approaching the TLP and CLP, especially when confronting harsh scenarios with a high obstacle density or with irregular geometries, such as the one proposed in this paper. In the results section, the performance of the designed methodology is analyzed, comparing the different fitness strategies for CLP optimization in order to attain the best solution.

4. Results

In this section, a case study of a hostelry scenario is presented to evaluatethe performance of the proposed algorithm.The selected scenario is based on Gaudi’s Casa Botines, a multipurpose establishment with a significant capacity, represented in Figure 8. The high density of obstacles present within the proposed scenario added to the irregularity of the valid location environment and the overall size constitute an arduous approach for allocating customers within the establishment.

Traditional approaches may fail when trying to allocate the maximum number of chairs while maintaining a certain interpersonal distance. On the other hand, table and chair distribution techniques present in the literature may result in suboptimal solutions due to the severe constraints introduced by the scenario geometry. Therefore, the selected scenarios represent an ideal case study for testing and analyzing the performance of the designed technique in all its variants.

Once loading the scenario into the sequential optimization, following the diagram present in Figure 2, the algorithm commences with the TLP optimization. All simulations were performed in the Python programming language, version 3.8.1, executed with an Intel^® i7 2.4 GHz of CPU and 16 GB of RAM. The simulations were executed with the list of hyperparameters shown in

Table 1. List of hyperparameters for the TLP LS MA optimization, adjusted experimentally following the methodology exposed in [50].

Parameter	Value
Number of Individuals	300
Stop Criteria	300 Generations or 90% Population Equal
Number of Points	16,384
Number of Possible Solutions *1	$3.68\times {10}^{109}$
Elitism Percentage	15%
Selection Technique	Tournament 3
Crossover Technique	Multi-Point 3
Mutation Percentage	12% Population 12% Genotype
$d_s$, $d_w$	1.5 and 0.3 m
$\epsilon$, Z	2.5, 100
Table Dimensions	1.9 × 0.9 m
$C_1,C_2,C_3$	1, 0.5, 1.5
$C_4$ *2, $C_5,C_6$	$7+0.03·{\mathit{gen}}^{-1}$, 14, 2
$\kappa ,X_{\mathit{lim}}$ *3	300, [0, 6]
$a,b$	[1.5, 1.3, 1.25], 2
${\mathit{LS}}_{\mathit{Criteria}}$	1 per 15 generations
${\mathit{LS}}_{\mathit{Individuals}}$	20
$n_t,n_s$	8, 10

*¹ Resulting from the combinatorial nature of the TLP [17] for 26 table distributions. *² $gen$ is the number of underwent generations. *³  $X_{\mathit{lim}}$ represents the limits of the random variable X.

.

The outcome of the TLP optimization, depicted in Figure 9, represents the optimized table distribution for a total of 26 tables, a significant number of tables within the scenario of study while respecting the stated restrictions. This figure represents the result of the first stage of the sequential optimization approach, and also the starting point for the posterior optimization of the chair arrangement.

The achieved distribution of Figure 9 exploits the available space in the scenario periphery and between obstacles, increasing the interpersonal distancing among tables, reaching a mean interpersonal separation of 3.28 m with a minimum distance separation of 2.4 m. Furthermore, while some deviation is present in the distance distribution, the algorithm achieves adequate uniformity in the achieved solution, reaching a standard deviation of 0.72 m.

Once optimizing the tables, their positions are fixed in place, and the second phase of the sequential optimization takes place—the LS MA CLP optimization.

Table 2. List of hyperparameters for the CLP LS MA optimization, adjusted experimentally through the procedure stated in [50].

Parameter	Value
Number of Individuals	400
Stop Criteria	400 Generations or 90% Population Equal
Number of Points	2500
Number of Possible Solutions *1	$N>1.29\times {10}^{305}$
Elitism Percentage	15%
Selection Technique	Tournament 3
Crossover Technique	Variable Segmentation
Mutation Percentage	15% Population 20% Genotype
$d_c,L_0$	1 m, 50 bits
$C_1,C_2,C_3$	10, 5, 1
$a,b$	[1.5, 1.3, 1.25], 2
${\mathit{LS}}_{\mathit{Criteria}}$	1 per 10 generations
${\mathit{LS}}_{\mathit{Individuals}}$	30
$n_s,n_c$	300, 90
$C_7,C_8,C_9$	15, 1.5, 2
$X_{\mathit{lim}}$	[0, 4]

*¹ Resulting from the combinatorial nature of the CLP [17] for 105 chair distributions.

details the different hyperparameters adjusted for the proposed algorithm.

Through the previously detailed hyperparameters, multiple LS MA optimizations are executed. A comparison among the different MDP optimization strategies is proposed in search of the best-suited technique for the CLP and for the presented scenario of study. The results of each optimization strategy are detailed in

Table 3. Comparison among the different MDP optimization strategies for the CLP.

Strategy	Mean Dist	Min Dist	Standard Deviation
Max-mean	2.72 m	0.05 m	1.14 m
Min-max	2.49 m	1.08 m	1.01 m
Max-sum	2.39 m	0.02 m	1.26 m
Mix	2.53 m	1.08 m	1.01 m

.

Results show that while the maximum mean distancing value is obtained by the max-mean strategy, the associated minimum distance yields no benefit for such an establishment. Similarly, the max-sum approach also fails to provide a valid distribution. These two optimization functions only favor the global distancing, in both mean value and total sum, and thus they fail at providing a more distributed arrangement.

On the other hand, both the min-max and the mix optimization strategy attain valid distributions, reaching good metrics in mean and minimum distancing, with a low standard deviation. However, the min-max optimization method only focuses on improving the absolute minimum distance, and while the resulting mean value is also favorable, the obtained distance distribution is less efficient than that attained by the mix strategy, as depicted in Figure 10.

While the analyzed metrics of the mix and min-max strategies display a certain similarity, their difference is noticeable when comparing the resulting distance distributions. The min-max strategy only takes into account the overall minimum value, attaining in the process a valid and distributed chair arrangement. However, this methodology is deficient when it comes to optimizing chairs with a low distance profile but greater than the global minimum distance.

Consequently, in Figure 10, a concentration of distances is perceptible in the proximity of the minimum distances, which is unfavorable for the overall quality of the distribution. On the other hand, the proposed methodology takes into consideration multiple metrics, pursuing a uniform distance profile with the gross of the distances of higher value to that of minimum distance, yet with a sufficient minimum separation. Based on these results, a mixed strategy could be the most desirable approach for most hostelry establishments, striking an adequate balance between mean and minimum distancing.

The achieved distance distribution from the proposed methodology is desirable both for decreasing the contagion probability and also for providing a more pleasant and attractive distribution for the establishment, where a certain degree of symmetry and order is appealing to the customer. The described order can be appreciated within the resulting chair distribution, shown in Figure 11, where a certain pattern is repeated throughout the tables.

Nevertheless, the proposed methodology orients these patterns in a way that, while attaining the optimal local distance profile within the table, the distancing among adjacent tables is also optimized. Furthermore, when allocating a number of chairs not divisible by the number of tables—such is the case of the proposed optimization—the algorithm also determines the optimal table for introducing the higher number of chairs, allocating them to the most distanced tables.

Therefore, the proposed methodology proves valuable for optimally allocating a certain number of customers over a determined certain. The proposed optimization strategy also achieves a distance profile, favorable both for sanitary purposes and for customer appeal. The proposed methodology is also adaptable to different scenarios, admitting varying and limiting restrictions while achieving a near-optimal solution, thus fulfilling the main objectives of this paper.

5. Conclusions

Devising a table and chair distribution to accommodate all customers is a significant challenge for many hospitality businesses, especially for multipurpose establishments that must regularly rearrange tables and chairs for daily service. This challenge not only affects the operational efficiency of businesses but also has important social and economic implications. Optimizing the use of space can lead to an increase in customer capacity, which can significantly boost revenue while ensuring safety and comfort for patrons. Additionally, for venues hosting large events, the ability to increase the maximum occupancy without compromising organization is vital for successfully accommodating a larger number of attendees.

Solutions for this problem are analyzed throughout the literature, where varying methodologies are proposed for attaining a valid solution. However, these approaches fail at optimizing both table and chair distribution in addition to other constraints such as the presence of obstacles or the effect of irregular scenarios. The combinatorial nature of these optimization problems combined, being each problem categorized as NP-Hard, with the addition of these constraints constitute an optimization problem yet unresolved in the literature.

In this paper, a sequential memetic algorithm optimization is proposed for attaining a near-optimal solution for the TLP and CLP combined. The proposed procedure implements a multiphase optimization procedure, where the algorithm first obtains the optimal coordinates of each table that maximize the distancing among tables, computed with respect to a chair location environment where chairs are placed.

The second phase of the optimization attains the optimal chair locations for the previously distributed tables. Different optimization strategies utilized throughout the literature are compared with a specifically designed procedure for obtaining the best-suited solution for these establishments.

The proposed methodology is then implemented into a realistic hostelry scenario with multiple constraints regarding table and chair placement and minimum interpersonal separation. The obtained results prove the viability of the presented methodology, where the specifically designed CLP optimization attains the best-suited distributions for such scenarios. Furthermore, the flexibility of the designed procedure also supports the introduction of additional constraints regarding event celebrations (i.e., performances and ceremonies) or other restrictions of diverse nature.