key: cord-0169662-29fg2puh
authors: Emu, Mahzabeen; Chandrasekaran, Dhivya; Mago, Vijay; Choudhury, Salimur
title: Validating Optimal COVID-19 Vaccine Distribution Models
date: 2021-02-03
journal: nan
DOI: nan
sha: d3d666642e6d4f33667dcaad358476d8a621e409
doc_id: 169662
cord_uid: 29fg2puh

With the approval of vaccines for the coronavirus disease by many countries worldwide, most developed nations have begun, and developing nations are gearing up for the vaccination process. This has created an urgent need to provide a solution to optimally distribute the available vaccines once they are received by the authorities. In this paper, we propose a clustering-based solution to select optimal distribution centers and a Constraint Satisfaction Problem framework to optimally distribute the vaccines taking into consideration two factors namely priority and distance. We demonstrate the efficiency of the proposed models using real-world data obtained from the district of Chennai, India. The model provides the decision making authorities with optimal distribution centers across the district and the optimal allocation of individuals across these distribution centers with the flexibility to accommodate a wide range of demographics.

The ongoing pandemic caused by the Severe Acute Respiratory Syndrome Coronavirus 2 (SARS-CoV-2) called the coronavirus disease (COVID- 19) , has not only caused a public health crisis but also has significant social, political, and economic implications throughout the world [2, 13, 19] . More than 92.1 million cases and 1.9 million deaths have been reported worldwide as of January 2021 [6] . One of the widely used solutions, in preventing the spread of infectious diseases is vaccination. Vaccination is defined by WHO as "A simple, safe, and effective way of protecting people against harmful diseases before they come into contact with them. It uses the body's natural defenses to build resistance to specific infections and makes the immune system stronger" 1 . Various researchers and pharmaceutical corporations began research work on identifying potential vaccines to combat the spread of COVID-19. Of the number of vaccines under trial, Tozinameran (BNT162b2) by Pfizer and BioNTech, and mRNA-1273 by Moderna have achieved an efficacy of more than 90% [12, 15] . Various nations have begun the process of approval of these vaccines for mass distribution and have placed orders to facilitate a continuous flow of supply of vaccines to meet the demands.

In this paper we propose a Constraint Satisfaction Programming (CSP) framework based model to optimize the distribution of vaccine in a given geographical region. We aim to maximize the distribution of vaccine among the group of the population with higher priority while minimizing the average distance travelled by any individual to obtain the vaccine. In order to justify the efficiency of the proposed model we compare the performance of the following four optimization models namely, and present how the model PD-VDM provides the most optimal solution for the distribution of vaccines. We perform a Case Study using the demographic data obtained from Chennai -a well-renowned city in Southern India. This case study highlights how the model can be used by decision making authorities of a city with an population of 5.7 million. The model aids the decision making authorities to choose an optimal number of vaccine distribution centers (DCs), and to optimally assign an individual to a hospital such that the individuals in the priority groups are vaccinated first while minimizing the distance they travel to the vaccine DCs. In section 2 we discuss the various steps and challenges involved in the process of vaccine distribution, in section 3 we describe in detail the procedure followed to build the proposed models. The case-study is discussed in section 4 followed by the discussion of results in section 5. We conclude with future research directions in section 6.

In order to effectively distribute vaccines, it is necessary to understand the supply chain of vaccines. The supply chain of vaccines is divided into four major components namely the product, production, allocation, and finally the distribution [7] . The first concern of the decision making authorities is to decide on which vaccine to choose for distribution in their country, province, or region. For example, for countries in tropical regions, the storage temperature of the vaccine is an important factor. Similarly, while developed countries are able to afford vaccines at a higher price, most developing countries prefer the vaccine which has an affordable price. In the present scenario, three of the prominent vaccines in play are the BNT162b2, mRNA-1273, and AZD1222 [10] . They have storage temperatures of -70℃, -20℃, and 0℃ and cost USD 20, USD 50, and USD 4 respectively 2 . Based on the storage it is safe to assume that while countries in temperate regions like the United States, Canada, and Russia would have the option of purchasing any one of these vaccines while tropical countries like India, Bangladesh, Pakistan would prefer AZD1222. The cost of the said vaccines also has a significant impact on the decision-making process of developing nations which mostly cater to a greater number of people. Once the product is chosen, the production of vaccines has to be scheduled according to the demand. Factors that are taken into consideration at this stage include the production time, capacity for manufactures, supply-demand analysis, and so on [3] . Depending on the stage of the epidemic and the severity, the demand for the vaccine and the optimal timeline for the supply of vaccines may vary. Allocation and distribution stages go hand in hand in the vaccine supply chain. Depending on the distribution strategy, the allocation of vaccines at any level is tuned to achieve the best result. Allocation at a global level may depend on priority established through contracts and agreements among pharmaceuticals and governments. However, once a country receives the vaccines, further allocating the vaccines to provinces, states, or subgroups of the population is a critical decision that in turn has an impact on the distribution strategy. The distribution stage of the supply chain addresses the challenges of establishing an effective routing procedure, infrastructure of the vaccine distribution centers, inventory control, workforce, etc. Operation Research (OR) involves the development and use of various statistical and mathematical problem-solving strategies to aid in the process of decision making. Various OR models are proposed over time to optimize the distribution of vaccines from the distribution centers. Ramirez-Nafarrate et al. [17] proposes a genetic algorithm to optimize the distribution of vaccines by minimizing the travel and waiting time. Huang et al. [9] formulated a vaccine deployment model for the influenza virus that ensures geographical priority based equity in Texas. However, their mathematical model might have generalization issues when applied to smaller or larger than state-level regions. Lee et al. [11] developed the RealOpt © a tool to aid in identifying optimal location for vaccine distribution centers, resource allocation and so on. Researchers have also provided models to accommodate specific locations, for example Aaby et al. [1] proposes a simulation model to optimize the allocation of vaccine distribution centers at Montgomery county, Maryland. This model aims to minimize the vaccination time and increase the number of vaccinations. While the above models consider the distribution centers to be stationary, Halper et al. [8] and Rachaniotis et al. [16] consider the vaccine distribution centers to be mobile and address this as a routing problem. While the later model proposes that various mobile units serve different nodes in a network, the latter considers that a single mobile units serves various areas with a goal to minimize the spread of infection. Some of the OR models used in epidemics' control include non-linear optimization, Quadratic Programming (QP), Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) [5] . ILP, MILP, and QP models are not suitable for many practical use cases due to its time expensive nature and infeasibility issues prevailing with irrational model designs. The mathematical design process and selection of pre-defined numerical bounds can lead to several technical glitches in the models. Despite the apparent similarities with ILP and MILP, CSP can eliminate all the aforementioned drawbacks and ensure sub-optimal solution in non-deterministic polynomial time by applying boolean satisfiability problem formulation. In the field of computer science, CSP is considered as a powerful mechanism to address research challenges regarding scheduling, logistics, resource allocation, and temporal reasoning [4] . Hence in this article we employ CSP to propose four models to optimize the distribution minimizing the traveling distance and maximizing the vaccination of high priority population.

In this section, we initially determine the optimal number and location of vaccine DCs using K-medoids clustering algorithm. Provided with the various locations of possible vaccine DCs, the algorithm determines the optimal number of clusters into which the region can be divided into, in order to effectively distribute the vaccines across the chosen region. On selecting the number of clusters and the cluster heads, we further propose four different vaccine distribution simulation models to optimize vaccine distribution based on two factors namely distance and priority. The clustering algorithm and the simulation models are explained in the subsections below.

Our proposed Algorithm 1 imitates the core logic of K-medoids clustering technique [14] . Firstly, the algorithm determines the optimal number of vaccine DCs to be selected from a set of hospitalsH based on silhouette score analysis [18] , as mentioned in line number 1. We determine the silhouette score for 2 tohH −1 number of potential vaccine DCs, whereH = {h 1 ,h 2 ,h 3 , ...,hH}. Then, we select the optimal number of vaccine DCs as η that retains the highest silhouette score. As per the line number 2, we randomly select η hospitals as vaccine DCs into H. Later, we initiate the clustering process. Each hospital is assigned to its closest vaccine DC to form η clusters, according to line numbers 5 − 8. The cluster informations indicating which hospital is associated to which vaccine DC are recorded in C. Next, the algorithm reassigns the vaccine DCs H to the ones with the minimum total distance to all other hospitals under the same cluster, executed in line numbers 9 − 16. We let the algorithm repeat the entire clustering process until vaccine DC assignments do not change. Hence, the termination criteria depends on the stability of the clustering process. To summarize, we employ this algorithm with inputs of a set of hospitals/potential vaccine DCs, H and a 2D dist matrix defining the distances of one hospital to every other hospital. The output of the algorithm is the set of optimally selected vaccine DCs H based on the distance metric. The primary idea is to choose vaccine DCs Validating Optimal COVID-19 Vaccine Distribution Models v Algorithm 1: K-medoids algorithm to choose vaccine DCs from a set of hospitals Input:H: A set of hospitals, dist: Squared matrix representing the distances of one hospital to every other hospital Result: H: A set of COVID-19 vaccine DCs 1 η ← Determine the number of optimal vaccine distribution centers using silhouette score 2 H ← Randomly select η hospitals fromH

optimally in a sparse manner to facilitate reachability for people living in any part of the considered region.

In this subsection, we proceed by explaining the system model for vaccine distribution. We denote H = {h 1 , h 2 , h 3 , ..., h H } to be the set of COVID−19 vaccine distribution centers selected by Algorithm 1, where H ⊆H and h i is the i th vaccine DC in H. Moreover, we define U = {u 1 , u 2 , u 3 , ..., u U } as the set of available staff, where every u j ∈ U i . We denote U i as the available set of staff in vaccine DC h i and U i ⊆ U. Subsequently, we can infer that U = ∪ |H| i=1 U i . We further assume that E = {e 1 , e 2 , e 3 , ..., e E } represents the set of people required to be vaccinated, and the k th person is e k . In order to specify the priority of people for vaccination purpose, we use the set P = {p 1 , p 2 , p 3 , ..., p P }. Hence, p k defines the priority level of a person e k ∈ E, and |E| = |P|. It is noteworthy that, the higher the priority level, the faster the vaccination service deployment is desired. The distance between a distribution center h i ∈ H and a specific person e k ∈ E is represented using D i,k . In this research, we consider the solution binary decision variable as x i,j,k ∈ {0, 1}. The value of the decision variable x i,j,k is 1, in case a distribution center h i ∈ H allocates a staff u j ∈ U i to vaccinate a person e k ∈ E, otherwise remains 0.

In this paper, we formulate the opted vaccine distribution research enigma as a CSP model. The CSP framework includes a set of aforementioned decision variables that should be assigned values in such a way that a set of hard constraints are satisfied. Hard constraints are essential to be satisfied for any model to reach a feasible solution. Suppose, our proposed model iterates over T = {t 1 , t 2 , ..., t T } times to complete vaccination, where each time instance t n ∈ T refers to per time frame for vaccine deployment decision making. Finally, N represents the total amount of available vaccine throughout the entire time periods T . All of our proposed CSP based models are subject to the following hard constraints that have been translated into integer inequalities, for any time frame t n ∈ T :

C1 :

The constraint C1 verifies that every staff from any distribution center can vaccinate at most one person at a time. Thus, for every staff u j ∈ U i of distribution center h i ∈ H, either there is a unique person e k ∈ E assigned for vaccination, or the staff remains unassigned. Then, constraint C2 ensures that every person e k ∈ E is allocated at most one vaccine through a single staff u j ∈ U i from a unique distribution center h i ∈ H. Finally, C3 is a binary constraint representing the value of decision variable to be 1, in case a staff u j ∈ U i of distribution center h i ∈ H is assigned to vaccinate a person e k ∈ E, otherwise 0, as mentioned previously. C4 :

The constraint C4 confirms that the total vaccine distribution should not be more than the available vaccine by any means throughout the entire periods T considered for vaccine deployment. Now, let us assume Ω be the set of all the feasible solutions that satisfy all hard constraints.

Apart from hard constraints, our proposed CSP formulation incorporates a set of soft constraints as well. Whilst hard constraints are modeled as inequalities, soft constraints are outlined through expressions intended to be eventually minimized or maximized. Soft constraints are not mandatory for finding a solution, rather highly desirable to improvise the quality of the solutions based on the application domain. The soft constraint C5 strives to maximize the number of overall vaccinated people. The focus of another soft constraint C6 remains to vaccinate the people with higher priority levels beforehand. In other words, this constraint leads to maximize the summation of priorities of all vaccinated people. Subsequently, the soft constraint C7 refers that every people should be vaccinated by staff from the nearest vaccine distribution center.

By B-VDM is a rudimentary vaccine distribution model that solely concentrates on the soft constraint C5 to maximize the overall vaccine distribution, irrespective of any other factors. A gain co-efficient α has been introduced to the ultimate objective function of the model in Eq. 9.

P-VDM ensures maximum vaccine distribution among the higher priority groups of people, by reducing soft constraints C5 and C6 into one objective function in Eq. 10. We denote β as the gain factor associated to soft constraint C6.

Contrarily, D-VDM encourages vaccination of the people located closer to distribution centers. This model can be specifically useful for rural regions, where distribution centers and people are sparsely located, including higher travelling expenses. For this model, we incorporate soft constraints C5 and C7, by multiplying gain coefficients α and γ, respectively.

Finally, the PD-VDM merges all the soft constraints simultaneously. Our proposed PD-VDM considers maximization of vaccine distribution in priority groups and minimization of distance factored in transportation expenditure, collaboratively. Furthermore, α, β, and γ have been introduced as gain factors to equilibrate the combination of soft constraints and then presented as a multiobjective function in the Eq. 12. Hence, this model can optimize priority and distance concerns conjointly based on the adapted values of gain factors.

The gain parameters of all the proposed models can be tuned to balance or incline towards more focused convergent vaccine distribution solutions. For instance, α, β, and γ are individually responsible for maximum distribution, maximization of priorities, and minimization of distance focused vaccine distribution solutions, respectively. Moreover, the policymakers can exploit these models and adjust gain parameters according to the region specifics and domain knowledge of vaccine distribution centers and population density. The regulation of these gain factors can aid to analyze and figure out the applicability of our various proposed models relying on different contextual targets, environment settings, and demand-supply gaps.

We demonstrate the proposed models using real-world data obtained from one of the popular cities in the southern part of India -Chennai. As listed by Rachaniotis et al. [16] most of the articles in literature make various assumptions to demonstrate the performance of their models, Similarly, we make a few reasonable assumptions to accommodate the lack of crucial data required to implement the model. Various input parameters of the models and their method of estimation or assumptions made to reach the decisions are described below.

• The entire city is divided into 15 zones for administrative purposes and we assume the distribution of vaccines is carried out based on these 15 zones as well. • To determine the vaccine distribution centers, we assume that the vaccines will be distributed from hospitals or primary health centers. While there are approximately 800 hospitals in Chennai, based on 'on-the-ground' knowledge, we select 45 hospitals (3 hospitals per zone) to enable us to determine the distance between the hospitals. The selected hospitals are classified as private (PVT) and public funded (PUB) based on their administration. At least one publicly funded hospital or primary health center is chosen per zone. • A 45 x 45 distance matrix is constructed with each row and column representing the hospitals. The cells are populated with the geographic distance obtained from Google Maps 3 . Using these distance measures, the optimal vaccine DCs are chosen by implementing k-medoids clustering algorithm described in Section 3.1.

• Total population to be vaccinated (E): As per the census records collected in 2011, Chennai has a population of 4.6 million distributed across an area of 175 km 2 with a population density of 26,553 persons/km 2 . Based on the growth in the overall population of India, we estimate the current population of Chennai to be 5,128,728 with a population density of 29,307/km 2 . • Set of Vacccine Distribution centers (H): The optimal vaccine DCs are chosen from using the clustering phase of the model using silhouette width such that the chosen DCs are evenly spread across the entire district.

• Staff for vaccination per DC (U): Based on the capacity of the hospital in terms of facilities, workforce, etc. the hospitals are classified as 'SMALL', 'MED', and 'LARGE'. We assume that small, medium, and large hospitals allocate 5, 20, and 40 health-care workers for vaccination purposes respectively. • Priority levels (P): While the priority levels can be decided by the authorities based on wide variety of parameters, for our simulation we assume that the priority depends on the age of the individual such that the elderly people are vaccinated earlier. The distribution of population across various age groups is calculated based on the age-wise distribution calculated during the census 2011. Table 1 shows the distribution of the population across six priority groups. Table 1 : Distribution of the population of Chennai across 6 age groups

• Time per vaccination (t): Based on the data provided during the recent trial dry run carried out in India, the government estimates to carry out 25 vaccinations in 2 hours span, we approximate that the time taken for the vaccination of one person to be 5 minutes. • Time per vaccination (N ): Keeping in mind the deficit in the supply of vaccines in the early stages of vaccination we assume that only vaccine doses for 50% of the total population is available currently. However, the number can be increased based on increase in production 4

These described parameters can be tuned by the decision making authorities to accommodate the distribution at the area under consideration. For all the experimental settings, we consider the gain factors α, β, and γ as 1 4 × | |, 1 4 × 1 |P| × | |, and 1 respectively. Yet, as mentioned earlier, these gain factors can be explored and set according to the solutions desired by policy makers and decision making authorities.

We demonstrate the proposed models in two scenarios with randomly generated data and two scenarios with real world data from Chennai. We discuss in detail the inferences from each scenario in this section. In each scenario we compare the four models and highlight how PD-VDM optimizes the two parameters taken into consideration -priority and distance.

For the two random scenarios we consider that there are 12 vaccine DCs in total and based on the silhouette width measures as shown in Fig. 1a we select three DCs optimally distributed across the area. We assume the total population size (E) to be 200 and the total number of vaccines available (N ) to be 85. Of the three chosen DCs we assume that each has a capacity (U) of 15, 30, 45. The model considers five different different priority levels (P) with 1 being the least and 5 being the most. The population is distributed among these priority levels as shown in Table 2 The distribution of vaccines at any time instance t n by all four models, for both random cases is depicted in Fig. 2 . The percentage of individuals vaccinated in each priority group in random case 1 and random case 2 are depicted in Fig.3a and Fig. 3b respectively. The B-VDM vaccinates 41.86%, 37.14%, 42%, 46.67%, and 44.44% of individuals across priorities 1 to 5 respectively, in both RC1 and RC2. We can see that 55.56% of the individuals from the highest priority group are left out. The D-VDM optimizes only the distance parameter and vaccinates 37.21%, 51.43%, 38%, 51.11% and 33.33% of individuals across priorities 1 to 5 respectively in RC1 and almost the same results in RC2. Again we can notice, that a greater percentage of the individuals in the highest priority group are not vaccinated. While both P-VDM and PD-VDM attempt to vaccinate 100% of the high priority individuals in both RC1 and RC2, on studying the average distance travelled by each individual of the population as depicted in Fig. 4a , we can clearly identify that the PD-VDM reduces the distance parameter by more than 40% in both RC1 and RC2 . We can also see that the 'distribution of population' parameter does not impact the performance of the models and PD-VDM is the 

In both the case-study scenarios we consider that the vaccination process continues for five hours each day and as mentioned in Section 4 each vaccination takes (t n ) 5 mins. Hence there are 60 vaccinations carried out by each health care worker for any given day. We compile and present the results of the vaccination process at the end of any given day. Although in the initial stages of the vaccination it is likely that individuals from one priority group will only be vaccinated, as time progresses people across various priority groups will need to be considered. Hence the population considered by the model for each day is taken as a stratified sample from the age-wise distribution of the overall population of Chennai provided in Table 1 . Initially we identify the optimal number of DCs needed for effectively serving the district of Chennai based on the distance between the hospitals considered. On analyzing the silhouette width of various 'number of clusters' as depicted in Fig. 1b we present two different scenarios namely,

• Case study scenario -1 (CS1): Three optimal DCs • Case study scenario -2 (CS2): Twelve optimal DCs

Case study scenario -1: For this scenario, we consider 3 optimal vaccine DCs (H) with capacities (U) of 5, 20, 40 since the chosen DCs fall under 'SMALL', 'MED' and 'LARGE' respectively. Based on these factors the total population to be vaccinated (E) in any given data is estimated to be 3,900. As mentioned in Section 4 we assume, that the total vaccines (N ) available to be half the total population which in this case sums upto 1,950. The entire population falls under six priority groups (P) based on their age. The actual number of people in each priority group is provided in Table 3 .

Case study scenario -2: For this scenario, we consider 12 optimal vaccine DCs (H) and among these 12 chosen DCs there are 3, 2 and 7 DCs with a staff capacity (U) of 5 ('SMALL'), 20 ('MED'), and 40 ('LARGE') respectively. Hence the total population (E) that can be vaccinated at any given 5 hour day is 20100. Similar to scenario 1 we assume that the total vaccines (N ) available to be half the total population which amounts to 10,050 and that the population is distributed across six different priority groups (P) based on their age as shown in Table 3 .

The vaccination percentage across the priority groups for both case study scenarios are provided in Fig. 3c and Fig. 3d respectively. Unlike the random scenarios, it is interesting to note that in both CS1 and CS2, the B-VDM though not optimized to satisfy a specific hard constraint, it produces results that are almost identical to P-VDM vaccinating 100% of the highest priority group individuals. This can be attributed to the similarity in the effect of α and β gain paramters in both these models in CS1 and CS2. Though the PD-VDM model vaccinates less than 90% of the individuals in the three highest priority groups we can clearly see that it significantly reduces the 'average distance travelled' by an individual in the population by more than 70%, which makes it more efficient than all the other models. While D-VDM achieves the least 'average distance travelled' value it sacrifices vaccinating almost 50% of the high priority groups. Thus, we demonstrate how PD-VDM efficiently distributes the available vaccines by modifying various parameters like the distribution of population, total population, total number of available vaccines, the number of vaccine DCs and the capacity of each DCs. The model provides flexibility for the decision-making authorities of any given demographic to optimize the distribution of vaccine in the desired region.

In this paper, we propose an optimization model (PD-VDM) based on Constraint Satisfaction Programming framework to find the most effective way to distribute vaccines in a given demographic region, in terms of distance and a priority (age, exposure, vulnerability, etc). We compare the efficiency of the model with three other models which take into consideration either one or none of the two optimization constraints. While this model can be adapted across a wide variety of scenarios as demonstrated in our case studies, it is essential to understand that due to resource constraints we have demonstrated only two of the many available constraints. Expanding the scope of the model to allow optimizing a wide variety of parameters can be carried out in future research, along with an attempt to replace some of the assumptions made in our model with real world data.

Montgomery county's public health service uses operations research to plan emergency mass dispensing and vaccination clinics

COVID-19: Disease, management, treatment, and social impact

Supply and demand uncertainty reduction efforts and cost comparison

Propositional satisfiability and constraint programming: A comparative survey

Allocating resources to control infectious diseases

An interactive web-based dashboard to track COVID-19 in real time

Literature review: The vaccine supply chain

The mobile facility routing problem

Equalizing access to pandemic influenza vaccines through optimal allocation to public health distribution points

COVID-19 Vaccine: A comprehensive status report

Advancing public health and medical preparedness with operations research

COVID-19: Moderna vaccine is nearly 95% effective, trial involving high risk and elderly people shows

The socio-economic implications of the coronavirus and COVID-19 pandemic: A review

A simple and fast algorithm for K-medoids clustering

Safety and efficacy of the BNT162b2 mRNA COVID-19 vaccine

A deterministic resource scheduling model in epidemic control: A case study

Point-of-dispensing location and capacity optimization via a decision support system

Silhouettes: A graphical aid to the interpretation and validation of cluster analysis

Impact of COVID-19 pandemic on mental health in the general population: A systematic review