A Robust Seating Arrangement for Future Pandemics

Abstract

Numerous studies have examined classroom seating arrangements to enhance student safety and resource utilization during COVID-19. These studies typically aimed to maximize the minimum distance between students for a given number of students to be assigned. This paper distinguishes itself from the existing literature by not only assigning students as far apart as possible but also focusing on maximizing the average distance between students. We call this new problem the maximum diversity social-distancing problem (MDPs), a novel variant of the maximum diversity problem (MDP). This problem is a two-phased problem, where the first phase involves producing the maximum of minimum distance (max-min) between students, and once that is resolved, the max-min distance is used in the second phase for having the highest dispersion. The first phase is here solved by a new algorithm, which effectively determines max-min distance for each student allocation scenario. For the second phase, three exact and one greedy approximation MDPs models are proposed. In computational testing, we observe that the greedy approximation MDPs model mostly returns optimal solutions across all tested classrooms in less than a second. More importantly, utilizing the greedy one significantly improves student pair spacing, increasing the average distance by over 40 centimeters compared to the max-min distance approach of the literature. Later, this effective approach is integrated into the pandemic management platform, which proactively assists the university administration in preparing for and effectively managing future infection outbreaks.