{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T12:33:12Z","timestamp":1776688392396,"version":"3.51.2"},"reference-count":35,"publisher":"Public Library of Science (PLoS)","issue":"2","license":[{"start":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T00:00:00Z","timestamp":1739232000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.plosone.org"],"crossmark-restriction":false},"short-container-title":["PLoS ONE"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1371\/journal.pone.0318380","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T18:27:16Z","timestamp":1739298436000},"page":"e0318380","update-policy":"https:\/\/doi.org\/10.1371\/journal.pone.corrections_policy","source":"Crossref","is-referenced-by-count":1,"title":["A simulated annealing with graph-based search for the social-distancing problem in enclosed areas during pandemics"],"prefix":"10.1371","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4053-2605","authenticated-orcid":true,"given":"Bayram","family":"Dundar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"340","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"pone.0318380.ref001","unstructured":"E. Mathieu, H. Ritchie, L. Rod\u00e9s-Guirao, C. Appel, C. Giattino, J. Hasell, et al, Coronavirus pandemic (COVID-19), Our World in Data, 2020. [Online]. Available: https:\/\/ourworldindata.org\/coronavirus"},{"issue":"5","key":"pone.0318380.ref002","doi-asserted-by":"crossref","first-page":"976","DOI":"10.3201\/eid2605.190995","article-title":"Nonpharmaceutical measures for pandemic influenza in nonhealthcare settings\u2014social distancing measures","volume":"26","author":"M.W. Fong","year":"2020","journal-title":"Emerging Infectious Diseases"},{"issue":"7","key":"pone.0318380.ref003","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1377\/hlthaff.2020.00608","article-title":"Strong social distancing measures in the United States reduced the COVID-19 growth rate","volume":"39","author":"C. Courtemanche","year":"2020","journal-title":"Health Affairs"},{"key":"pone.0318380.ref004","unstructured":"National Center for Immunization and Respiratory Diseases (U.S.). Division of Viral Diseases, \u201cSocial distancing: Keep a safe distance to slow the spread [Updated July 15, 2020],\u201d July 15, 2020. [Online]. Available: https:\/\/stacks.cdc.gov\/view\/cdc\/90580"},{"issue":"12","key":"pone.0318380.ref005","doi-asserted-by":"crossref","first-page":"e0289998","DOI":"10.1371\/journal.pone.0289998","article-title":"Recommended distances for physical distancing during COVID-19 pandemics reveal cultural connections between countries","volume":"18","author":"D. Chai","year":"2023","journal-title":"PloS One"},{"key":"pone.0318380.ref006","doi-asserted-by":"crossref","first-page":"140430","DOI":"10.1016\/j.scitotenv.2020.140430","article-title":"Effect of the social distancing measures on the spread of COVID-19 in 10 highly infected countries","volume":"742","author":"T. P. B. Thu","year":"2020","journal-title":"Science of the Total Environment"},{"issue":"1","key":"pone.0318380.ref007","doi-asserted-by":"crossref","first-page":"3737","DOI":"10.1038\/s41467-021-24115-7","article-title":"Association of social distancing and face mask use with risk of COVID-19","volume":"12","author":"S. Kwon","year":"2021","journal-title":"Nature Communications"},{"issue":"2","key":"pone.0318380.ref008","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1080\/01605682.2021.1971575","article-title":"Seat assignment models for classrooms in response to Covid-19 pandemic","volume":"74","author":"B. Dundar","year":"2023","journal-title":"Journal of the Operational Research Society"},{"key":"pone.0318380.ref009","doi-asserted-by":"crossref","first-page":"102390","DOI":"10.1016\/j.scs.2020.102390","article-title":"The efficacy of social distance and ventilation effectiveness in preventing COVID-19 transmission","volume":"62","author":"C. Sun","year":"2020","journal-title":"Sustainable Cities and Society"},{"issue":"4","key":"pone.0318380.ref010","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1111\/j.1538-4632.1987.tb00133.x","article-title":"Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems","volume":"19","author":"M.J. Kuby","year":"1987","journal-title":"Geographical Analysis"},{"key":"pone.0318380.ref011","doi-asserted-by":"crossref","unstructured":"K.S. Dhir, F. Glover, and C.-C. Kuo, Optimizing diversity for engineering management, in Proceedings of engineering management society conference on managing projects in a borderless world, IEEE, 1993, pp. 23\u201326.","DOI":"10.1109\/IEMC.1993.316510"},{"issue":"1","key":"pone.0318380.ref012","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/j.amc.2006.11.090","article-title":"Iterated tabu search for the maximum diversity problem","volume":"189","author":"G. Palubeckis","year":"2007","journal-title":"Applied Mathematics and Computation"},{"issue":"1","key":"pone.0318380.ref013","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.ejor.2006.01.021","article-title":"Tabu search and GRASP for the maximum diversity problem","volume":"178","author":"A. Duarte","year":"2007","journal-title":"European Journal of Operational Research"},{"key":"pone.0318380.ref014","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s10589-007-9161-6","article-title":"Hybrid heuristics for the maximum diversity problem","volume":"44","author":"M. Gallego","year":"2009","journal-title":"Computational Optimization and Applications"},{"key":"pone.0318380.ref015","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s10479-011-0898-z","article-title":"A simple and effective algorithm for the MaxMin diversity problem","volume":"186","author":"D.C. Porumbel","year":"2011","journal-title":"Annals of Operations Research"},{"key":"pone.0318380.ref016","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s10732-011-9172-4","article-title":"Heuristics and metaheuristics for the maximum diversity problem","volume":"19","author":"R. Mart\u00ed","year":"2013","journal-title":"Journal of Heuristics"},{"key":"pone.0318380.ref017","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.engappai.2013.09.005","article-title":"A tabu search based memetic algorithm for the maximum diversity problem","volume":"27","author":"Y. Wang","year":"2014","journal-title":"Engineering Applications of Artificial Intelligence"},{"issue":"2","key":"pone.0318380.ref018","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/j.ejor.2020.07.053","article-title":"Measuring diversity. A review and an empirical analysis","volume":"289","author":"F. Parre\u00f1o","year":"2021","journal-title":"European Journal of Operational Research"},{"key":"pone.0318380.ref019","first-page":"1","volume-title":"Handbook of Metaheuristics","author":"D. Delahaye","year":"2019"},{"key":"pone.0318380.ref020","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.eswa.2018.12.048","article-title":"A fast simulated annealing algorithm for the examination timetabling problem","volume":"122","author":"N. Leite","year":"2019","journal-title":"Expert Systems with Applications"},{"issue":"3","key":"pone.0318380.ref021","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1016\/j.ejor.2017.08.035","article-title":"A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints","volume":"265","author":"L. Wei","year":"2018","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"pone.0318380.ref022","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0305-0548(03)00206-5","article-title":"Simulated annealing heuristics for managing resources during planned outages at electric power plants","volume":"32","author":"A.R. McKendall","year":"2005","journal-title":"Computers & Operations Research"},{"key":"pone.0318380.ref023","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.amc.2013.07.022","article-title":"Dynamic robot path planning using an enhanced simulated annealing approach","volume":"222","author":"H. Miao","year":"2013","journal-title":"Applied Mathematics and Computation"},{"issue":"3","key":"pone.0318380.ref024","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1007\/s10589-011-9442-y","article-title":"Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem","volume":"52","author":"S. Anand","year":"2012","journal-title":"Computational Optimization and Applications"},{"issue":"12","key":"pone.0318380.ref025","doi-asserted-by":"crossref","first-page":"e0243345","DOI":"10.1371\/journal.pone.0243345","article-title":"Planning for classroom physical distancing to minimize the threat of COVID-19 disease spread","volume":"15","author":"A. T. Murray","year":"2020","journal-title":"PloS One"},{"key":"pone.0318380.ref026","doi-asserted-by":"crossref","first-page":"110829","DOI":"10.1109\/ACCESS.2024.3441767","article-title":"A robust seating arrangement for future pandemics","volume":"12","author":"G. Karakose","year":"2024","journal-title":"IEEE Access"},{"key":"pone.0318380.ref027","doi-asserted-by":"crossref","first-page":"102737","DOI":"10.1016\/j.omega.2022.102737","article-title":"Social distancing and revenue management\u2014A post-pandemic adaptation for railways","volume":"114","author":"M.T. Haque","year":"2023","journal-title":"Omega"},{"key":"pone.0318380.ref028","doi-asserted-by":"crossref","first-page":"101691","DOI":"10.1016\/j.jth.2023.101691","article-title":"Seat allocation optimization for railways considering social distancing during the post-pandemic period","volume":"33","author":"G. Xu","year":"2023","journal-title":"Journal of Transport & Health"},{"key":"pone.0318380.ref029","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s40314-021-01718-w","article-title":"A support tool for planning classrooms considering social distancing between students","volume":"41","author":"J.C. Bortolete","year":"2022","journal-title":"Computational and Applied Mathematics"},{"key":"pone.0318380.ref030","doi-asserted-by":"crossref","first-page":"42985","DOI":"10.1109\/ACCESS.2021.3065298","article-title":"Seat assignments with physical distancing in single-destination public transit settings","volume":"9","author":"J.F. Moore","year":"2021","journal-title":"IEEE Access"},{"issue":"1","key":"pone.0318380.ref031","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/s12076-023-00331-1","article-title":"Physical distancing as an integral component of pandemic response","volume":"16","author":"A.T. Murray","year":"2023","journal-title":"Letters in Spatial and Resource Sciences"},{"issue":"1","key":"pone.0318380.ref032","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/s43762-022-00040-3","article-title":"GIS-based classroom management system to support COVID-19 social distance planning","volume":"2","author":"T. Lokhande","year":"2022","journal-title":"Computational Urban Science"},{"issue":"1","key":"pone.0318380.ref033","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.ejor.2021.07.010","article-title":"Safe distancing in the time of COVID-19","volume":"304","author":"M. Fischetti","year":"2023","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"pone.0318380.ref034","doi-asserted-by":"crossref","first-page":"3294","DOI":"10.1111\/itor.13139","article-title":"On the optimal layout of a dining room in the era of COVID-19 using mathematical optimization","volume":"29","author":"C. Contardo","year":"2022","journal-title":"International Transactions in Operational Research"},{"issue":"6","key":"pone.0318380.ref035","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1111\/j.1540-5915.1993.tb00509.x","article-title":"Analyzing and modeling the maximum diversity problem by zero-one programming","volume":"24","author":"C.-C. Kuo","year":"1993","journal-title":"Decision Sciences"}],"container-title":["PLOS ONE"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0318380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T18:27:28Z","timestamp":1739298448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0318380"}},"subtitle":[],"editor":[{"given":"Zhengmao","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2025,2,11]]},"references-count":35,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2,11]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pone.0318380","relation":{},"ISSN":["1932-6203"],"issn-type":[{"value":"1932-6203","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,11]]}}}