Simultaneously minimizing the health and economic impacts of Covid-19 is the biggest challenge for countries and industries as the lockdown has become the first line of defense against Covid-19 and many countries have gone through the lockdown phase [1] . As the economic damages of Covid-19 have become unbearable as a result of lockdown, countries have begun the reopening phases and have allowed their businesses to reopen to avoid the catastrophic economic effects of Covid-19 [2, 3] . In the reopening phases many businesses and countries have implemented social distancing measures as it has been strongly argued to be the most effective non-pharmacological way to reduce the health impact of Covid-19 [1] . Complementary methods such as washing hands and using masks have been also recommended strongly or enforced by businesses and governments. Additionally, many new products such as physical barriers, covers and protocols have been introduced to the market to help different businesses implement social distancing measures more rigorously and reduce the health risk of Covid-19 for their on-site employees and customers [4] . However, the main way of applying the social distancing measures has been through leaving empty spaces between people using signages on floors and seats. These signages have been installed in simple ways such as leaving empty rows or columns of seats between people to create social distancing (usually 6 feet). To the best of our knowledge, it seems that none of the businesses and industries have used modeling and optimization methods to maximize the number of people on-site and their distances, under a social distancing constraint, to decrease the health and economic impacts of Covid-19. Our modeling and optimization methods could be applied to a variety of settings, such as classrooms, restaurants, theaters, medical centers and etc.
In this paper we report the results of optimizing the number of passengers and their arrangements under a social distancing measure for the airline industry by introducing a model. In our model we introduce the quantity Spread and by applying simulated Annealing Monte Carlo we minimize Spread to obtain the optimum number and arrangement of passengers for two types of single and twin aisle aircraft layouts under a social distancing measure. We show that our obtained optimal arrangements have higher distance between passengers as compared to any suboptimal arrangements with the same number of passengers. Our results suggest that it is necessary to use modeling methods to minimize the health and economic impacts of Covid-19 under social distancing measures.
We introduce our model based on the observed facts about spreading the SARS-CoV-2 virus as well as the social distancing measures that have been suggested by health experts and enforced or recommended by businesses and governments. Social distancing is the physical distance between two people and has been recommended to be 6 feet. In this model, family groups, or people who live together, do not need to follow the social distancing measure. However, individuals and groups that do not live together do need to follow the social distancing measure. Based on these facts, we introduce the below model with a quantity that we name Spread, and we minimize Spread to obtain the optimum number of passengers and their arrangements. We assume that we have a twodimensional problem with all people being assigned a position in an xy plane. Based on these facts we define the Spread for person i ( ) as follows:
where and − are, respectively, the distance and the distance in the y direction between individuals i and j, sd is the minimum social distancing that should be followed by individuals, = 1 and its unit is
Eq. 1 has four terms. The first and second terms keep the family members close to each other. Term ( − ) 2 in the second equation dictates that the members of a family group sit close to each other on the same row and term ( − 2) 2 dictates that the members of the same family group stay as close as possible to each other. We should note that other terms such as ( − ) 2 , where n = 3, 4, …, might be added to the second term if it is desirable to keep big family groups close to each other. The third equation in our model is the penalty for not following the social distancing measure for people that do not belong to the same family group. The fourth equation keeps people who are not in the same family group as far as possible from each other and it acts as a repulsion force. We define the total Spread as sum of the individual Spreads as follows:
Where sum is over all on-site people and our goal is to minimize to obtain the maximum distance between non-group individuals who follow the social distancing measure. Since the number of passengers under the social distancing is less than the number of seats, the number of possible arrangements of passengers is ( ), where and are the number of seats and the number of passengers, respectively. The number of possible arrangements can grow exponentially; for instance, for a half-filled aircraft with 96 seats, the number of possible arrangements is ~ 2 96 ~ 8 × 10 28 . Hence, we use the simulated Annealing Monte Carlo [5, 6] approaches to minimize and obtain the optimal arrangements and number of passengers.
In this work we consider two popular seat layouts in aircrafts, namely, single (Fig. 1a) and twin (Fig. 1b) aisles cabin layouts for the economy class. The same model could be applied to the business class. The single aisle layout has 16 rows, with 6 seats in each row, separated evenly by an aisle, making a total of 96 seats (Fig 1a) . The twin aisle layout has 17 rows, with 7 seats in each row, 2 seats on either side and 3 seats in the center, making a total of 119 seats (Fig. 1b) . These single and twin aisle layouts correspond to popular seat layouts in Boeing 737-800 and Boeing 767, respectively. There are, however, variations of these layouts. In both of these layouts, we consider that the distance between two adjacent seats is one unit, the distance between a seat and its front and back seat is 1.8 units, and the width of the aisle is one unit as well (Fig. 1) . Fig. 1 . The arrangement of seats and the unit distance we used in our models for single aisle (a) and twin aisle (b) seat layouts. We assume that the distance between adjacent seats in one row is one unit and the distance of a front and back seat in the same column is 1.8 units.
We use Spread, the quantity that we introduced in the Model section and minimize Spread to obtain the arrangement that maximizes the distance between passengers. As we explained in the Model section, we use the simulated Annealing Monte Carlo (AMC) to find the minimum Spread. In the Method section we discuss in detail the Algorithm that we use to minimize Spread.
We begin with cases in which the passengers are a combination of individual passengers and family groups with different number of members and the social distancing guideline of 2.25 units, where unit is defined in the Seat Layouts and Parameters section. Throughout the rest of the paper and in the figures, we show the individual passengers with white masks and family groups with the same color masks. We consider three different cases of passengers as follows: (a) one four-member, two three-member, and four two-member family groups (b) three four-member, one three-member, and five twomember family groups and, (c) four three-member and five two-member family groups in a single layout aircraft. For each of these cases, we maximized the number of individual passengers that can be fitted to the seats under the social distancing measure (2.25 units). In Fig. 2 , we show the optimal arrangements of passengers for the mentioned three cases under the social distancing measure. Fig. 2 . The optimal arrangements of passengers for (a) one four-member, two three-member, four two-member family groups and eighteen individual passengers (b) three four-member, one threemember, five two-member family groups and thirteen individual passengers (c) four three-member and five two-member family groups and fourteen individual passengers. The arrangements of family groups and individual passengers are determined by the model such that it maximizes the distance between non family group members. Therefore, the location of family groups changes based on the number of family groups and individual passengers.
Our results show that the maximum number of individual passengers that can be fitted to the seats for cases (a), (b) and (c) are eighteen, thirteen, and fourteen, respectively. We observe that, in all these arrangements, family group members are correctly located close to each other and in the same row, when possible, and individual passengers and groups members who do not belong to the same family group follow the social distancing measure. Moreover, when possible, our model keeps the family members as close as possible to each other. This can be seen clearly in the family group with pink masks in Fig. 2b in which the fourth group member is seated in the middle seat close to all the three family members in the back seats. When it is not possible to keep the family members as close as possible, our model correctly shifts a family member to another seat (groups with blue masks in Figures. 2a and 2b) to maximize the number of passengers. Also, in these arrangements, family groups and individual passengers are spread without any specific pattern as the model maximizes the distance between passengers that do not belong to a family group. For example, In Fig. 2a , two of the two-member family groups in rows 12 and 16 are separated by three rows and two of them with one row (seated in rows 1 and 3) as opposed to Fig. 2c where all two-member family groups are separated, one after the other, by one row (rows 8, 10, 12, 14), with one two-member family group located in the top left seats (row 16). We can observe the same behaviors for three-member and four-member family groups in Figures 2a, 2b and 2c . We should also note that there are a large number of arrangements in which only two passengers don't follow the social distancing guidelines (not shown here). In some of these arrangements, all the passengers need to be rearranged to find the optimal arrangement in which passengers follow the social distancing guidelines. Our model, along with simulated Annealing Monte Carlo, is clearly able to distinguish these arrangements from the optimal arrangement that follows the social distancing measures. Moreover, in many cases, there are arrangements that have the same number of passengers with the same number of groups and individual passengers as the optimal arrangement, with passengers following the social distancing measures as well, however, the distances between passengers are not maximized. We refer to these arrangements as suboptimal arrangements, and in the next section we discuss them in detail. Our model is clearly able to distinguish between these suboptimal arrangements and the optimal arrangement and find the optimal arrangement.
We have done extensive simulations for different cases of groups and individual passengers to find the optimal arrangements and number of passengers and then compare them with suboptimal arrangements. In Fig. 3 , we show our results for the average total distance between non family passengers per passenger for these cases for a single aisle layout. These results demonstrate that the average total distance could be increased by more than 10% in the optimal arrangements as compared to suboptimal arrangements. We also find that some of the arrangements do not have suboptimal arrangements or, in some cases, suboptimal arrangements have an average total distance which is very close to the optimal arrangements. We should note that finding the optimal number and arrangements of passengers is almost impossible by trial and error.
To investigate the optimal and suboptimal arrangements in more detail, we discuss one case with two four-member, three three-member, and five two-member family groups for single and twin aisles layouts. We begin with the single aisle layout and find that the maximum number of individual passengers that can be fitted with these groups is eleven passengers. In Fig. 4a , we demonstrate the optimal arrangement of passengers for the groups along with eleven individual passengers. In Fig. 4b, we show a suboptimal arrangement, which, as we defined, has the same numbers of groups and individual passengers as the optimal arrangement, and passengers follow the social distancing measure. To compare the difference between these two arrangements, in Figures 5a and  5b , we, respectively, plot the distance of passengers from other passengers for the optimal and suboptimal arrangements corresponding to the seat arrangement in Figures  4a and 4b . For clarity in the colorbar, we not only show the distance but also the percentage that each color occupies in the plots. From these plots, we see that the red area in the optimal arrangement occupies less area than in the suboptimal arrangement. This demonstrates that, in the optimal arrangement, the overall distance between passengers is higher although the number of passengers in both arrangements is the same, and, in both arrangements, the social distancing measure is followed. Fig. 3 . The average total distance between non family passengers per passenger for some optimal arrangements versus suboptimal arrangements. The optimal arrangements are shown by full blue circles and suboptimal arrangements by orange stars. There might be more than one suboptimal arrangement for each optimal arrangement. The number of groups and individuals are shown in x-axis as tuples with the following structure (Number of four-member family group, Number of three-member family group, Number of two-member family group, Number of individual passengers). Some of the suboptimal arrangements have a closer average total distance as compared to others, depending on the number of groups, number of members in groups, and number of individual passengers. Also, the number of suboptimal arrangements changes from case to case, depending on the number of groups, number of members in groups and number of individual passengers. In some cases, suboptimal arrangements are very close to optimal arrangements. The arrangement of passengers with two four-member, three three-member and five twomember family groups and eleven individual passengers in the optimal (a) and suboptimal (b) arrangements. In both arrangements the social distancing measure is followed by passengers. Fig. 5 . The counterplot of distance of passengers from other passengers for the optimal (a) and suboptimal (b) arrangements corresponding to Figures 4a and 4b , respectively. From these plots we see that the suboptimal arrangement has a higher red area than blue, which means that the distance of passengers is higher in the optimal arrangement than the suboptimal arrangement. In the colorbar we show the percentage that each color occupies in the plots.
Since passengers who are close to each other have higher health impacts on each other we define quantity = 1 ∑ 1/ , to measure the health impact of close non family passengers to a passenger (passenger ) with the assumption that this impact decreases with the inverse of distance between passengers (1/ ). In this equation is the distance between passenger and and the sum is over all the non family groups that are in the range of 4.3 units distance from passenger .
has the dimension of distance and we refer to it as effective distance throughout the rest of this paper, and it decreases as the distance between passenger and other non family passengers who are in their vicinity of 4.3 units decreases. We use 4.3 units to only consider the health effects up to three possible nearest passengers. In Figures 6a and 6b we respectively plot effective distance for the two arrangements corresponding to Figures 4a and 4b and in the colorbar we not only show the color related to each effective distance but also the percentage that each color occupies in the arrangement. and suboptimal (b) arrangements corresponding to the passengers' arrangements in Figures 4a  and 4b , respectively. For clarity, we show the percentage that each color occupies in each plot in the corresponding colorbars. Although a few passengers in the suboptimal arrangement have higher effective distance as compared to others, this is at the cost of all other passengers sitting closer to each other. Overall, in the optimal arrangement, passengers have higher effective distance from each other as compared to the suboptimal arrangement.
Interestingly, from the first look it seems that in the suboptimal arrangement the dark green seats, which corresponds to highest effective distance, occupy 5.3% as compared to the optimal arrangement in which they occupy 2.6%. However, looking more closely we observe that in the optimal case the percentage of passengers that have the closest effective distance (violet color) is 23.7% as compared to 36.8% for the suboptimal arrangement. In addition, gold and light green seats in the optimal case occupy 55.3% and 18.4%, respectively, as compared to the suboptimal arrangement in which gold and light green seats occupy 42.1% and 15.8%. Therefore, in the optimal arrangement, the overall effective distance between passengers is maximized as opposed to the suboptimal arrangement in which a few passengers are seated farther away from others at the cost of making all other passengers seated closer to each other. We should add that seats with higher effective distances can be assigned to passengers that are more vulnerable to Covid-19.
For the second case, we consider a twin aisle layout with the same number of family groups as the single aisle layout and find the optimum number of individual passengers that can be fitted to the seats. Our results show that the optimal number of individual passengers that can be fitted to the seats with the groups is nineteen. In Fig. 7a we demonstrate the optimal arrangement and, similarly to the single aisle case, we show the results of a suboptimal arrangement with the same number of groups and individual passengers (Fig. 7b) . To compare these two arrangements, in Figures 8a and 8b we show the distance of each passenger from other passengers corresponding to the arrangements in Figures 7a and 7b . The bigger red area for the suboptimal arrangements clearly shows that in the optimal arrangement the distance between passengers is higher than in the suboptimal arrangement. In Figures 9a and 9b , we, respectively, plot the effective distance (defined in the previous section) of each passenger from other passengers corresponding to the passenger arrangements in Figures 7a and 7b . From these two plots we clearly see that, overall, the passengers in the optimal arrangements have a higher effective distance than suboptimal arrangement. This could be seen more clearly from the percentage of area that each color occupies (shown in the colorbar). Unlike the single aisle case, in this case, we observe that in the optimal arrangement the dark green area occupies 8.7% of the seats as compared to 4.3% for the suboptimal arrangement. This shows that, in some cases, our model not only maximizes the overall distance between passengers but also creates more seats that have the highest distance from other seats as compared to suboptimal cases. We should also add that, in the optimal arrangement, the light green, gold and violet seats occupy 13.0%, 32.6%, and 45.7% of seats, respectively, as compared to the suboptimal case, in which light green, gold, and violet occupy 13%, 19.6%, and 63.0% of seats, respectively. Fig. 7 . The arrangement of passengers with two four-member, three three-member, and five twomember family groups and nineteen individual passengers in the optimal (a) and the suboptimal (b) arrangement. In both arrangements, the social distancing measure is followed by passengers. Fig. 8 . The counterplot of distance of passengers from other passengers for the optimal (a) and suboptimal (b) arrangements corresponding to Figures 7a and 7b , respectively. From these plots, we see that the suboptimal arrangement has a higher red area than blue which means that the distance between passengers is higher in the optimal arrangement than the suboptimal arrangement. In the colorbar, we show the percentage that each color occupies in the plots. . 9 . The average distance of each passenger from other passengers for optimal and suboptimal arrangements corresponds to the passengers' arrangements in Figures 7a and 7b , respectively. For clarity we show the percentage that each color occupies in each plot in the corresponding colorbar. Overall, in the optimal arrangement passengers have higher effective distance from each other as compared to the suboptimal arrangement.
Social distancing measures, which have been imposed by governments to reduce the health impacts of Covid-19, have had a big impact on businesses that have on-site customers as they have had to limit their on-site capacity. These businesses have mostly implemented social distancing by installing signages that block some spaces and guide customers to keep the recommended distance from other customers. However, to the best of our knowledge, they have not used modeling and optimization methods to optimize the number of people and their arrangements on their sites. In this study, we introduced a model with quantity Spread, and we proposed that by minimizing Spread, it is possible to maximize the number of people and their distances for social distancing measures on a site. To illustrate this, we studied a real-world case from the airline industry and optimized the number of passengers and the arrangements of passengers for the single and twin aisles aircraft layouts using AMC method. We showed that our model correctly arranges the family members groups close to each other and maximizes the distance between non family members. Moreover, we demonstrated that our obtained arrangements of passengers have higher distance between passengers than any suboptimal arrangement with the same number of passengers and a social distancing measure. The optimal arrangements of passengers have complex patterns, which depend on the number of groups, the number of members in each group, and the number of individual passengers. Our results clearly show that the optimal arrangements of passengers minimize the health and economic impacts of Covid-19 by maximizing the number of passengers and their distances under a social distancing measure. Moreover, we demonstrated that among the seats that are allocated to passengers, some seats have higher effective distances from other seats. These seats could be assigned to passengers who are more vulnerable to Covid-19 to reduce the health impact of Covid-19. These results clearly show that our model or its variants, along with optimization methods such as Annealing Monte Carlo method, must be utilized to minimize the health and economic impacts of Covid-19 for businesses that have on-site employees and customers. Our model could be applied to various organizations and companies with onsite people such as classrooms, theaters, restaurants, sporting events, waiting rooms, medical centers, etc.
As it was discussed in the Model section our aim is to find the positions of family groups and individual passengers by minimizing Spread ( ) using Annealing Monte Carlo simulation. Below we use the terms individual and individuals as a replacement for person and people.
We start the simulation by assigning a random position to all individuals as the first AMC step. In each AMC step, we apply Monte Carlo simulation to find the local minimum of Spread for individuals. In every MC step, each individual (i) is allowed to minimize their own Spread by moving one step in a direction based on the Metropolis Hastings Algorithm [7] : = {1, exp (−( − )/ )}. If the Spread of the individual cannot be accepted, the individual does not move. At each AMC step, we decrease T and change the position of an individual randomly. Then we allow all individuals to find their optimum positions based on the Metropolis-Hastings algorithm. This algorithm is "capitalistic" in nature, as each individual lowers only their own Spread. This does not automatically mean that finds its global minimum.
The algorithm used in our code can be described in more details as below:
•Start. Get initial individual positions randomly as trial positions.
• According to Eq. 2, we calculate of initial individual positions. • Start AMC with high temperature ( = 2.3 × 10 9 , 1 = and j = 1).
I. Get temperature (T), change position of an individual randomly and k = 0. A. While j < number Monte Carlo steps, go to rule 0 otherwise go to rule II.
Sort individual based on maximum and i = 1.
Calculate spreadi from Eq. 1.
Take spreadiold=spreadi.
Choose the new position of individual i in its eight neighbors randomly and calculate spreadinew. 4 .
Check if this new position is occupied with another individual. If it is occupied before, go back to rule 3. If its eight neighbors are occupied with another individuals go to rule 10. 5.
Calculate the difference between new and old spread for individual i: Δ = − . 6.
= min{1, exp(−∆ /T)}.
Get random number r. 8.
If ≥ , accept the new position and = . 9.
If > , individual should come back to its old position. 10.
i=i+1 and Sort individual based on maximum . 11.
If i < number individuals, go back to rule 1 otherwise j = j+1 then go to rule A. II. Calculate from Eq. IX. If > 10 −6 , = + 1 then go to rule I. Otherwise go to next part. • AMC cycle gets finished.