Abstract
In response to COVID-19, many countries have mandated social distancing and banned large group gatherings in order to slow down the spread of SARS-CoV-2. These social interventions along with vaccines remain the best way forward to reduce the spread of SARS CoV-2. In order to increase vaccine accessibility, states such as Virginia have deployed mobile vaccination centers to distribute vaccines across the state. When choosing where to place these sites, there are two important factors to take into account: accessibility and equity. We formulate a combinatorial problem that captures these factors and then develop efficient algorithms with theoretical guarantees on both of these aspects. Furthermore, we study the inherent hardness of the problem, and demonstrate strong impossibility results. Finally, we run computational experiments on real-world data to show the efficacy of our methods.
Similar content being viewed by others
Data Availability
All data and code for the experiments can be found at https://github.com/Ann924/MobileFacility.
References
COVID-19 Surveilance Dashboard. https://nssac.bii.virginia.edu/covid-19/dashboard/. Accessed 23 Jan 2022
See How Vaccinations Are Going in Your County and State. https://www.nytimes.com/interactive/2020/us/covid-19-vaccine-doses.html. Accessed 23 Jan 2022
Meet the Four Kinds of People Holding Us Back From Full Vaccination, New York Times. https://www.nytimes.com/interactive/2021/05/18/opinion/covid-19-vaccine-hesitancy.html
Celik Turkoglu, D., & Erol Genevois, M. (2020). A comparative survey of service facility location problems. Annals of Operations Research 292. https://doi.org/10.1007/s10479-019-03385-x
Drezner, Z., & Hamacher, H.W. (2002). Facility Location - Applications and Theory. Springer, ???. http://www.springer.com/computer/swe/book/978-3-540-42172-6
Chang, S., Pierson, E., Koh, P.W., Gerardin, J., Redbird, B., Grusky, D., & Leskovec, J. (2021). Mobility network models of covid-19 explain inequities and inform reopening. Nature 589
Wang, L., Ben, X., Adiga, A., Sadilek, A., Tendulkar, A., Ventatramanan, S., Vullikanti, A., Tambe, M., & Marathe, M. (2020). Using mobility data to understand and forecast covid 19 dynamics. medRxiv
Mehrab, Z., Wilson, M. L., Chang, S., Harrison, G., Lewis, B., Telionis, A., et al. (2022). Data-driven real-time strategic placement of mobile vaccine distribution sites. Proceedings of the AAAI Conference on Artificial Intelligence, 36, 12573–12579.
Tai, D.B.G., Shah, A., Doubeni, C.A., Sia, I.G., Wieland, M.L. (2020). The disproportionate impact of covid-19 on racial and ethnic minorities in the united states. Infectious Diseases Society of America
Afshari, H., & Peng, Q. (2014). Challenges and solutions for location of healthcare facilities. Industrial Engineering and Management, 2014, 1–12.
Hochbaum, D. S., & Shmoys, D. B. (1985). A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2), 180–184. https://doi.org/10.1287/moor.10.2.180.
Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293–306.
Hochbaum, D. S., & Shmoys, D. B. (1986). A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3), 533–550. https://doi.org/10.1145/5925.5933.
Bertsimas, D., Digalakis, V., Jr., Jacquillat, A., Li, M. L., & Previero, A. (2022). Where to locate covid-19 mass vaccination facilities? Naval Research Logistics (NRL), 69(2), 179–200.
Bravo, F., Hu, J., Long, E. (2022). Optimal covid-19 vaccination facility location. Available at SSRN 4008669
Shukla, S., Fressin, F., Un, M., Coetzer, H., & Chaguturu, S. K. (2022). Optimizing vaccine distribution via mobile clinics: a case study on covid-19 vaccine distribution to long-term care facilities. Vaccine, 40(5), 734–741.
Rader, B., Astley, C.M., Sewalk, K., Delamater, P.L., Cordiano, K., Wronski, L., Rivera, J.M., Hallberg, K., Pera, M.F., Cantor, J., et al. (2021). Spatial accessibility modeling of vaccine deserts as barriers to controlling sars-cov-2. medRxiv
Roy, S., Dutta, P., Ghosh, P. (2021). Generalizable multi-vaccine distribution strategy based on demographic and behavioral heterogeneity. In: 2021 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pp. 1495–1498. IEEE
Nedjati, A., & Valipour, M. (2012). Solving health care facility location problems with new heuristic algorithm method. International Journal of Modeling and Optimization. https://doi.org/10.7763/IJMO.2013.V3.225.
Meskarian, R., Penn, M.L., Williams, S., Monks, T.A. (2017). Facility location model for analysis of current and future demand for sexual health services. PLoS One
de Vries, H., van de Klundert, J., & Wagelmans, A. P. M. (2020). The roadside healthcare facility location problem a managerial network design challenge. Production and Operations Management, 29(5), 1165–1187.
Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R. (2020). A Technique for Obtaining True Approximations for \(k\)-Center with Covering Constraints
Harris, D. G., Li, S., Pensyl, T. W., Srinivasan, A., & Trinh, K. (2019). Approximation algorithms for stochastic clustering. Journal of Machine Learning Research, 20, 153–115333.
An, H.-C., Bhaskara, A., Svensson, O. (2013). Centrality of Trees for Capacitated k-Center
Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms (1st ed.). Cambridge: Cambridge University Press.
Inamdar, T., Varadarajan, K. (2018). On the Partition Set Cover Problem
Wolsey, L. A. (1982). An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4), 385–393. https://doi.org/10.1007/BF02579435.
Rajagopalan, S., & Vazirani, V. V. (1998). Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM Journal of Computing, 28(2), 525–540. https://doi.org/10.1137/S0097539793260763.
Lan, G., DePuy, G.W., Whitehouse, G.E. (2007). An effective and simple heuristic for the set covering problem. European Journal of Operational Research 176
Grossman, T., & Wool, A. (1997). Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research, 101(1), 81–92. https://doi.org/10.1016/S0377-2217(96)00161-0.
Gurobi Optimization, L. (2021). Gurobi Optimizer Reference Manual. http://www.gurobi.com
Perron, L., Furnon, V.: OR-Tools. https://developers.google.com/optimization/
Chen, J., Hoops, S., Marathe, A., Mortveit, H., Lewis, B., Venkatramanan, S., Haddadan, A., Bhattacharya, P., Adiga, A., Vullikanti, A., Srinivasan, A., Wilson, M.L., Ehrlich, G., Fenster, M., Eubank, S., Barrett, C., Marathe, M. (2021). Prioritizing allocation of COVID-19 vaccines based on social contacts increases vaccination effectiveness
Machi, D., Bhattacharya, P., Hoops, S., Chen, J., Mortveit, H., Venkatramanan, S., Wilson, B.L.M., Fadikar, A., Maiden, T., Barrett, C.L., Marathe, M.V. (2021). Scalable Epidemiological Workflows to Support COVID-19 Planning and Response
Acknowledgements
We express our sincere thanks to the referees for suggesting the experiments in Sect. 6.5 and the extension of capacity constraints. We also thank members of the Biocomplexity COVID-19 Response Team and the Network Systems Science and Advanced Computing (NSSAC) Division for their thoughtful comments and suggestions related to epidemic modeling and response support. George Li, Aravind Srinivasan, and Leonidas Tsepenekas were supported in part by NSF award number CCF-1918749. Ann Li, Madhav Marathe, and Anil Vullikanti were supported by DTRA (Contract HDTRA1-19-D-0007), University of Virginia Strategic Investment Fund award number SIF160, National Institutes of Health (NIH) Grants 1R01GM109718, 2R01GM109718, OAC-1916805 (CINES), CCF-1918656 (Expeditions), CNS-2028004 (RAPID), OAC-2027541 (RAPID), IIS-1908530, IIS-1955797, and IIS-2027848. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon.
Funding
George Li, Aravind Srinivasan, and Leonidas Tsepenekas were supported in part by NSF award number CCF-1918749. Ann Li, Madhav Marathe, and Anil Vullikanti were supported by DTRA (Contract HDTRA1-19-D-0007), University of Virginia Strategic Investment Fund award number SIF160, National Institutes of Health (NIH) Grants 1R01GM109718, 2R01GM109718, OAC-1916805 (CINES), CCF-1918656 (Expeditions), CNS-2028004 (RAPID), OAC-2027541 (RAPID), IIS-1908530, IIS-1955797, and IIS-2027848.
Author information
Authors and Affiliations
Contributions
AS and MM and AV came up with the problem formulation. GL and LT designed the algorithms. LT proved the hardness results. GL and AL wrote the code and generated the figures. All authors contributed to writing and reviewing the manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no financial or proprietary interests in any material discussed in this article.
Ethical Approval
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Li, G.Z., Li, A., Marathe, M. et al. Deploying vaccine distribution sites for improved accessibility and equity to support pandemic response. Auton Agent Multi-Agent Syst 37, 31 (2023). https://doi.org/10.1007/s10458-023-09614-9
Accepted:
Published:
DOI: https://doi.org/10.1007/s10458-023-09614-9