EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Bayram Dundar iD

PLOS ONE · 2025

DOI: 10.1371/journal.pone.0318380 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS ONE, 2025. Verfasst von Bayram Dundar. Beteiligte Einrichtung: Department of Industrial Engineering, School of Engineering, Architecture, and Design, Bartin University, Bartin, Turkey. Hauptthemen laut MEDLINE: Pandemics, COVID-19, Physical Distancing. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

PandemicsCOVID-19Physical DistancingHumansAlgorithmsComputer SimulationSARS-CoV-2

Autor:innen und Institutionen

  • Department of Industrial Engineering, School of Engineering, Architecture, and Design, Bartin University, Bartin, Turkey.

ORCID-Profile: Bayram Dundar

Zitieren

APA

Dundar, B. (2025). A simulated annealing with graph-based search for the social-distancing problem in enclosed areas during pandemics. PLOS ONE. https://doi.org/10.1371/journal.pone.0318380

Vancouver

Dundar B. A simulated annealing with graph-based search for the social-distancing problem in enclosed areas during pandemics. PLOS ONE. 2025. doi:10.1371/journal.pone.0318380

BibTeX
@article{Dundar2025,
  author = {Dundar, Bayram},
  title = {A simulated annealing with graph-based search for the social-distancing problem in enclosed areas during pandemics},
  journal = {PLOS ONE},
  year = {2025},
  doi = {10.1371/journal.pone.0318380}
}
Kostenlos starten →