Abstract

A territory-wide vaccination program will be launched in the first quarter of 2021 to protect people in Hong Kong from the impact of COVID-19 pandemic. To run a successful vaccination program with a limited supply of a vaccine, a methodology must be developed to efficiently provide vaccination to the people who need it. In this case study, we explore an optimization approach to plan a vaccination program for a vaccine under a limited supply. The vaccination problem may be formulated as a transportation problem that may be solved in two methods. The unique problem structure and solution methods give us an intuitive understanding of the original vaccination problem. Further, the same methods may be applicable for other vaccines which will be made available in Hong Kong in the near future.

Keywords: Vaccination, COVID-19, Transportation Problem, Optimization

Introduction

To reduce the impact of COVID-19 pandemic, Hong Kong Government enforces many disease containment regulations and rules including such as:

• A maximum limit of two persons in any outdoor group gatherings,
• Mask wearing required in any public places (both indoor and outdoor),
• No dine-in service from 6 p.m. to 5 a.m. (on the next day),
• A maximum limit of two persons allowed to share a table in a restaurant,
• A mandatory quarantine period for inbound travellers,
• A mandatory COVID-19 testing for certain people of close contacts to confirmed cases and of high-risk groups [1].

Although these measures are essential, they adversely affect the normal interaction of the people and the operation of the economy. Vaccination is expected to be an effective measure to stop the spread of the virus and put people’s life back to normal.

Hong Kong has already secured 3 different vaccines: AstroZeneca-Oxford, Biontech-Fosun, and Sinovac-Biotech [2]. Biontech-Fosun has recently been approved and will be used in Hong Kong. The maximum number of doses for Biontech-Fosun confirmed for Hong Kong is 7.5 million. This means that the maximum number of people covered by this vaccine is 3.75 million. People who are not getting the vaccine will have to choose the other two brands.

The supply of Biontech-Fosun vaccine will be delivered from Germany in batches over 6 months with the first shipment possibly at the end of February 2021. It is however impossible to get enough supply to satisfy all the people who want it all at once. The health authority plans to prioritize vaccination to certain groups in the population. Elderlies and healthcare professionals of clinics, hospital, and senior residential homes will be given higher priorities. While prioritized vaccination is an effective approach to contain an epidemic outbreak [4], it is also important to have a methodology to efficiently distribute the product to the people who are in need.

In this work, we examine the use of an optimization approach to make sure the supply meeting the demand and at the same time to minimize the cost. Specifically, we formulate this vaccination problem under a limited supply as a transportation problem [5]. With this specific transportation problem structure, the original vaccination problem may be solved with North West Corner Rule (NWCR) and Simplex Method. Through this discussion, we hope to provide a policy maker an intuitive understanding of the vaccination problem and the possible solution methods for planning this vaccination program.

Vaccination Problem

Total doses of Biontech-Fosun vaccine for Hong Kong are 7.5 million. We assume that the vaccine will be available in 6 shipments of 1 million, 1.5 million, 1.5 million, 1.5 million, 1 million and 1 million doses, respectively. Further, we assume that the shipment will arrive at Hong Kong at the end of a month and the product is ready for use at the beginning of the month. The shelf life of the vaccine is 6 months under cold storage at about -70 degrees Celsius.

The total population in 2019 is 7.451 million [3]. It is impossible to procure and secure enough doses to satisfy all the demand at once. Priorities must be given to most vulnerable members of the society and those who have higher risk of in-contact with the COVID-19 virus.  As of 2019, the number of medical professionals is 116,241 and the number of people aged 65 or above stands at 1.266 million. Each person needs two doses of the vaccine. In other words, medical professionals and elderlies consume 2.764 million doses. The remaining 4.736 million doses will be available for another 2.368 people. For a simple exposition of our methodology, we assume that the vaccination program of Biontech-Fosun completes in 7 months. The extra month is to ensure that people having their first shot done in Month 6 get the second shot in Month 7.  

Table 1 summarizes the demand and supply of the vaccine (in doses) in a transportation tableau which is used to represent the vaccination problem. The supplied doses each month are given in the last column and the demanded doses each month are given in the bottom row. The storage cost per dose per month (s) is significant. If a dose is kept for two months, its storage cost per dose for two months will be 2s. The shelf life of the vaccine is 6 months. Therefore, the storage cost for a dose kept beyond 6 months is a big number M where M >> s.

Other cost items may include for example the vaccine cost, the shipment cost from Germany, the relevant insurance cost, the operation cost of the vaccination centres, the manpower cost of the centres, the cost of the last mile delivery, etc.  These cost items are important in determining the total cost of the vaccination campaign but they are not relevant to the vaccination program we discussed in this work. For instance, the vaccine cost is sunk cost and has no impact on when the vaccine is used. The last mile delivery of a dose of the vaccine is also considered irrelevant as each dose must be shipped to a vaccination centre disregarding when the vaccine is used.

We do not consider backorder. This means that we do not allow the current demand to be met by a future supply. In other words, the current demand must be satisfied by the supplies available up to the current period. Hence, we assign a big number M to represent the storage cost per dose per month in all the backorder cells. A feasible solution can only have its entries in the diagonal cells and the upper cells along the diagonal minus Cell (1,7).

North West Corner Rule

With a transportation tableau, we demonstrate how to find a feasible solution using North West Corner Rule (NWCR) [6]. A feasible solution may not be an optimal solution. Stepping Stone Method (SSM) uses a feasible solution as a basis to find an optimal solution [6].

Table 2 shows the initial feasible solution of NWCR that ignores the cost of a cell in the tableau. We begin with Cell (1,1) by assigning the maximum available doses in Month 1 to completely satisfy the demand in the same month. Then we move one cell across and assign the remaining doses in Month 1 to partially satisfy the demand in Month 2. Further, we move one cell down and use the available doses in Month 2 to satisfy the rest of the demand in Month 2. The horizontal and vertical calculation from the most north-west cell will stop at the most south-east cell. NWCR will find us a feasible solution. The total cost of the solution is 12,700,000s. If s = HK$5.5 (or ~US$0.7097), the total cost will be HK$69,850,000 (or ~US$9,012,903).

Table 1: Transportation Tableau.

Table 2: Transportation Tableau after NWCR.

Certainly, this feasible solution may be used as a final solution for implementing the vaccination program. However, it is often true that we may find a better solution using this feasible solution as an initial solution. This is achieved by applying SSM. Table 3 shows one iteration of SSM.

SSM evaluates all the cells with no supply entry such as Cell (1,5) and checks if a supply entry given to Cell (1,5) (i.e., using the supply in Month 1 to satisfy the demand in Month 5) reduces the total cost. Suppose 1 dose is added to Cell (1,5). Then 1 dose will be deduced from Cell (4,5). The process follows the path in Table 3 involving horizonal and vertical movements until it gets back to Cell (1,5). The net cost change in this calculation chain of this path will be 5s-2s+s-2s+s-2s+s-2s = 0. This means that adding 1 dose to Cell (1,5) will not reduce the total cost. It turns out that none of the cells with no supply entry can reduce the total cost. Hence, the solution by NWCR is optimal.

Table 3: Transportation Tableau after one iteration of SSM.

Solution by Excel with Solver

Instead of solving the problem using a transportation tableau, we may formulate the vaccination problem using a Linear Programming (LP) approach. Let us define:

s	Storage cost per dose per month
cij	cij = (j – i + 1)s for 1 < j – i + 1 < 6; cij = M for j – i + 1 > 6; (The shelf-life of the vaccine more than 6 months) cij = M for j – i + 1 < 0; (No backorder is allowed)
ai	Supplied doses in Month i
bj	Demanded doses in Month j
Xij	Supplied doses in Month i to satisfy demanded doses in Month j

The LP formulation of the vaccination problem is given as follows:

Min	∑i ∑j cijXij
s.t.	∑j Xij = ai	i = 1,…,6
	∑i Xij = bj	j = 1,…,7
	Xij > 0	i = 1,…,6 and j = 1,…,7

The objective function of the LP formulation minimizes total cost. The first constraint ensures that the sum of the demands across all 7 months equals to the supply of a month. The second constraint ensures that the sum of the supplies over all 6 months equals to the demand of a month. The third constraint enforces the non-negative requirement for decision variables.

The problem can be solved by Simplex Method [5]. Many optimization packages are available for use. For illustrative purpose, we use Microsoft Excel with Solver Add-in as a solution platform. The advantages of Microsoft Excel are its ease of use and its accessibility. Figure 1 gives the spreadsheet formulation. In Figure 1(a), the storage cost per dose per month in an invalid cell such as Cell (1,7) is assigned a big number to prevent the invalid cell from being included in a solution. In Figure 1(b), decision variables X_ij are given in rows 18 through 23. The values in decision variables are arbitrarily assigned for checking spreadsheet equations. They do not affect the use of Solver. The value of the objective function is in Cell B28.

 

(a) Top section of the spreadsheet

(b) Bottom section of the spreadsheet

Figure 1: The vaccination problem formulated in a spreadsheet.

Figure 2 shows how Simplex Method is set up in Solver. The first entry in the dialog box is cell reference for the value of the objective function. We specify a minimization problem in the second entry. Cell references for decision variables X_ij are defined in the third entry. The first and second constraints are given in the constraint section. The box to enforce the non-negative requirement for decision variables is checked. Finally, Simplex Method is selected from a pull down menu. Click Option button next to the choice for solution methods and choose “Use Automatic Scaling”. Click Solve button to find a solution.

 

Figure 2: Dialog box for Solver.

The solution by Simplex Method (given in Figure 3) is different from the solution by NWCR but the values of the objective function are the same for both solutions. In other words, both solutions are optimal to the original problem. NWCR finds one optimal solution and Simplex Method finds another. Multiple optimal solutions happen in many optimization problems. The existence of multiple optimal solutions allow a decision maker to consider critieria for selection other than just optimization mechanics.  The solution by NWCR favors the use of the vaccine within two months while the solution by Simplex Method lets the vaccine kept beyond 2 months. Since the vaccine must be kept under cold storage, it is properly safer to consume the available vaccine doses as early as possible. Under this consideration, the solution by NWCR may be chosen, although both solutions have the same value of the objective function.

 

Figure 3: A Solver solution.

Conclusion

Motivated by the vaccination program in Hong Kong against COVID-19 pandemic, we make use of an optimizaton approach to efficiently provide the vaccination to the people who are in need. A transportation problem is used for meeting the demand and supply at the lowest cost. Two different solution methods are discussed. With a transportation tableau, North West Corner Rule (NWCR) may be used to generate a feasible solution. Stepping Stone Method (SSM) uses the feasibkle solution as a starting point to find an optimal solution. With a linear porgramming formulation, Simplex Method may be used to find an optimal solution. Through this dicussion, we hope to increase our understanding of the vaccination program under a limited vaccine supply. Although our formulation uses Biontech-Fosun vaccine as an example, it is also applicable to other vaccines which will soon be available in Hong Kong.

References

1. https://www.coronavirus.gov.hk/eng/index.html.
2. https://www.info.gov.hk/gia/general/202012/12/P2020121200031.htm.
3. https://www.dh.gov.hk/english/statistics/statistics_hs/files/Health_Statistics_pamphlet_E.pdf.
4. Cheng CH, Kuo YH, Zhou Z (2020) Outbreak minimization v.s. influence maximization: an optimization framework. BMC Medical Informatics and Decision Making 20: 266. [View]
5. Hillier FS, Lieberman GJ (2015) Introduction to Operations Research. (10edn) McGraw Hill, Gautam Buddha Nagar, Uttar Pradesh, India. [View]
6. Taylor BW (2019) Introduction to Management Science. (13edn). Prentice Hall Pearson, USA. [View]