3 May 2021
In this article we replicate an academic paper's model formulation of a COVID-19 vaccination plan for Hong Kong.
The model represents the supply of, and demand for, vaccine doses as a transportation problem, with doses "transported" from month-to-month given a storage cost rate. The objective is to minimize the total storage cost, while matching monthly supply and demand.
The paper's author solves the model using Excel and Solver. We do the same, though we also use OpenSolver – to see how it behaves differently. To incentivize the model to produce an intuitively better solution, we extend the model to include an escalating cost over time.
Download the models
The model is available on GitHub.
Situation
A COVID-19 vaccination program needs to be planned for Hong Kong. With a limited supply of vaccine, this case study explores an optimization approach to planning the vaccination program. The author develops a delivery plan based on a "transportation problem" model formulation.
Vaccine doses are scheduled to be supplied over a six month period, as shown in Figure 1. The figure also shows that, starting in the first month that doses are available, vaccinations are scheduled over a seven month period.
Vaccine doses can be stored for up to six months. It costs $5.50 per dose per month to store the vaccines. Our objective is to minimize the cost of storing the vaccines.
Model design
Heuristic solution method
The situation is represented as a transportation problem. That is, the vaccine doses are "transported" from supply months to demand months, as shown in Figure 2. In the figure, s represents the cost of storage, while M represents infeasible paths (implemented as a very high storage cost of $10,000 per dose per month).
For example, the supply of 1,000,000 doses in Month 1 is delivered to meet demand of 700,000 in Month 1 and contributes 300,000 doses to demand in Month 2. The remaining demand for Month 2 is met by doses supplied in Month 2. The storage cost of the 1,000,000 doses supplied in Month 1 is: 700,000 * (1 * 5.50) + 300,000 * (2 * 5.50) = $7,150,000.
The paper initially solves the transportation model using a heuristic. In this example, the heuristic finds an optimal solution, though that outcome is not guaranteed.
Linear programming formulation
The paper then formulates a linear programming (LP) model to solve the problem.
The LP formulation is straightforward:
- Minimize the cost of storing vaccine doses.
- Subject to requiring that monthly demand is met.
- And ensure that all supply is used within the modelling horizon.
Vaccine doses are inseparable, meaning that they cannot be divided into fractional units. Therefore, our model needs to allocate doses as integer quantities – which implies that we should formulate the model as an integer program, rather than a linear program. However, an interesting characteristic of transportation problems is that, given integer data, the solution will always be integer. Therefore, as proven by George Dantzig in 1951, we can use an easier-to-solve LP formulation.
Implementation
Specify the storage costs
Vaccines cost $5.50 per dose per month to store. The monthly incremental cost and cumulative costs are shown in Figure 3. In the spreadsheet we translate these costs into a month-by-month matrix, for convenience when calculating the "transportation" costs. Note that later we will escalate these costs by a penalty factor, but for now the cost is a constant monthly rate.
Allocate supply of doses to meet demand
Mirroring the matrix structure used in the paper, Figure 4 shows how the monthly supply of vaccines could be allocated to meet the monthly demand. For example, we expect to receive supply of 1,500,000 doses in Month 2, of which we plan to use 700,000 doses in Month 2, 200,000 in Month 3, 200,000 in Month 4, and 400,000 doses in Month 5.
Given a plan for the use of vaccine doses, we can calculate the total storage cost.
Solver model
Objective function
The Solver model is shown in Figure 5. Our objective is to minimize total cost of storing vaccine doses from when they arrive until when they are used.
Variables
The model has one set of variables:
vAllocation. The number of vaccine doses supplied in a month allocated to meet demand in that month or later months.
Constraints
The constraints are:
fDemandPerMonth = dDemandForDoses. Ensure that demand is met.fSupplyPerMonth = dSupplyOfDoses. Ensure that all supply is used.
Solution method
All of the model's relationships are linear, so we can use the Simplex method.
This model is sufficiently small that either Solver or OpenSolver can be used.
Analysis
Optimal solution
The optimal solution found by Solver is shown in Figure 6. The total cost of storing vaccines in $69,850,000. This is the same allocation and cost found by Solver as described in the paper.
Alternative optima
We already know that this problem has alternative optima – the heuristic and Solver find different solutions that have the same objective function value.
In this situation, there are many alternative optima. For example, if we solve the model using OpenSolver, rather than Solver, then we get another alternative optima, as shown in Figure 7. It is common for Solver and OpenSolver to find different optimal solutions – where alternative optima exist.
We ran the model on the 64-bit version of Excel 365 on Windows 10. If you're running different versions of the software or operating system, or with different hardware, then it is possible that you'll find different optima. This happens because the software and hardware environment can influence the specific steps that the solver takes, which may lead to different solutions.
Extending the model to minimize storage time
In the paper, the author initially used a heuristic to find a solution. The heuristic's solution has an intuitively favorable attribute: supplied doses are used as soon as they can be, given the supply and demand schedules. That is, batches of vaccine doses are stored for the minimum time possible for each batch.
Conversely, the solutions found by both Solver and OpenSolver store vaccines for up to two months, with gaps between when a batch of doses arrives and when some of it is used. Although the solutions are still optimal in terms of our objective of minimizing storage costs, they don't feel like the best solutions.
The solvers store doses because the cost of storing vaccine doses is linear. That is, if we need to store some doses until next month, then the solver is indifferent between storing vaccine doses that we already have versus storing vaccine doses that arrive this month or subsequently. This is the key reason why this model has many alternative optima – there are many ways to arrange the dose use over time, while storing doses for the same number of months overall.
However, we might prefer to use older doses first, perhaps because there is a risk of some doses becoming unusable, or simply because that intuitively seems like a more sensible solution. We can incentivize the solvers to use doses as soon as possible by adding an increasing penalty – such as a compounding percentage – on the storage costs. This is a useful technique for breaking the symmetry implied by having a constant storage cost rate.
If we set the penalty at +1% per month, then the storage costs are as shown in Figure 8.
Note that the model is still linear, even though the storage cost is non-linear, because the cost each month is a constant rather than being a non-linear function of variables. Also note that the numerical value of the penalty rate isn't especially important – any positive rate produces the same solution.
With a positive penalty on storage, such as +1% per month, both Solver and OpenSolver find the same optimal solution shown in Figure 9. Even though the objective function value hasn't changed (if we ignore the artificial penalty factor), this solution is more satisfactory as there are no gaps in the schedule. This is also the solution found by the heuristic, as described in the paper.
What happens if we use a negative penalty rate?
Interestingly, we can apply a negative penalty rate, such as -1% per month. This reduces the marginal storage cost over time, which creates an incentive to use supplied doses as late as possible (while still meeting the demand schedule).
Applying a negative penalty to the storage cost leads to a very different solution, as shown in Figure 10. The solution defers until Month 7 some of the batch we received in Month 2 – it does this because we told the model that it is better to use doses later. Such a solution doesn't make much sense in this situation, but there are other situations where a declining marginal cost might be a useful adjustment to apply.
Conclusion
This model is an example of using a transportation model to solve a vaccine scheduling problem in Excel.
Our model demonstrates that such a model may have many alternative optima. We also introduce a method of applying a non-linear penalty to incentivize the solver to use resources as soon as possible, leading to an intuitively more satisfactory solution.
If you would like to know more about this model, or you want help with your own models, then please contact us.
References
Cheng, CH. (2021). "Supply driven planning for a vaccination program in Hong Kong: An optimization approach", COVID-19 Pandemic: Case Studies & Opinions, Volume 2021, Issue 02, pages 196-202.