A simulated annealing with graph-based search for the social-distancing problem in enclosed areas during pandemics

Bayram Dundar

PLOS ONE, 2025, vol. 20, issue 2, 1-16

Abstract: During the pandemic, decision-makers offered many preventive policies to reduce the negative effects of the pandemic. The social distance rule in enclosed areas was implemented by educational institutions in any countries. In this study, we deal with the problem of assigning students to seats by considering the social distancing constraint and with objective of maximizing the total distance among the students. This problem is found to be similar to the Maximum Diversity Problem (MDP) in the literature. We name this new problem as Maximum Diversity Social Distancing problem (MDPs). A simulated annealing algorithm framework for MDPs (SA-MDPs) is proposed to identify an optimal or near-optimal solution within a reasonable computational time. A greedy random-based algorithm is presented to determine efficiently an initial feasible solution. The new neighborhood search procedure based on graph theory is introduced, in which the dominated, dominating, and nondominated seats are determined based on social distance. The proposed SA-MDPs is evaluated on classrooms with varying capacities and benchmarked against an off-the-shelf optimization solver. The computational tests demonstrated that the SA-MDP model consistently provided either proven optimal solutions or superior best-known solutions compared to a commercial solver, all within a reasonable CPU time.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0318380 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 18380&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0318380

DOI: 10.1371/journal.pone.0318380

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().