Heuristic algorithm tool for planning mass vaccine campaigns

Abstract

Purpose

The planning of massive vaccination campaigns often falls to nongovernmental organizations that have to face the critical challenge of vaccinating the largest number of people in the shortest time. This study aims to provide an easy tool for minimizing the duration of mass vaccination campaigns in rural and remote areas of developing countries.

Design/methodology/approach

This paper presents a linear mathematical model that combines location, scheduling and routing decisions that allows determining where to locate the vaccination centers, as well as the schedule/route that each medical team must follow to meet the target demand in the shortest time possible. In addition, the paper proposes an heuristic approach that can be integrated in a spreadsheet.

Findings

As the numerical experiments show, the proposed heuristic provides good solutions in a short time. Due to its simplicity and flexibility, the proposed approach allows decision-makers to analyze and evaluate several possible scenarios for decision-making by simply playing with input parameters.

Social implications

The integration of the heuristic approach in a spreadsheet provides a simple and efficient tool to help decision-makers while avoiding the need for large investments in information systems infrastructure by user organizations.

Originality/value

Motivated by a real-life problem and different from previous studies, the objective of the planning is to reduce the length of the vaccination campaigns with the available resources and ensure a target coverage instead of planning for minimizing costs or maximizing coverage. Furthermore, for helping implementation to practitioners, the heuristic can be solved in a spreadsheet.

Citation

Rodríguez-Pereira, J., Ramalhinho, H. and Sarrà, P. (2024), "Heuristic algorithm tool for planning mass vaccine campaigns", Journal of Humanitarian Logistics and Supply Chain Management, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/JHLSCM-09-2023-0082

1. Introduction

The equal access to health services is one of the most critical challenges in health care, especially in rural areas of developing countries. Ensuring healthy lives and promoting well-being for all at all ages figures among the 17 sustainable development goals (SDG) established by the United Nations General Assembly (2015) in the 2030 Agenda for Sustainable Development. In particular, the SDG 3, called “Good health and well-being,” seeks to achieve universal health coverage, including financial risk protection, access to quality essential health care services and access to safe, effective, quality and affordable medicines and vaccines for all. In that sense, the efforts made to increase the universal health coverage through immunization activities save millions of lives every year from more than 20 life-threatening diseases such as diphtheria, whooping cough, polio, influenza or measles. A WHO [1] and UNICEF report records that immunization currently prevents between 4 and 5 million deaths each year, but an additional 1.5 million deaths could be prevented by improving global vaccination coverage. Moreover, last indicators show the coverage has come to a standstill over the last decade, with a marked setback due to COVID-19 pandemic and associated disruption. Global coverage has fallen from 86% in 2019 to 81% in 2021, where we found the highest number of children missing out on vaccines since 2009.

Emergencies, pandemics and disease outbreaks hinder health progress, shorten life expectancy and hold up broader gains in education or economic development. In this context, ensuring solid vaccine distribution and deployment logistics under disrupted conditions can reduce capital and inventory costs and dignify the providing of essential health services. In that sense, the Global Vaccine Action Plan (GVAP) 2011–2020 was developed to eradicate vaccine-preventable infectious diseases, focusing on underserved communities. The GVAP goals included eradicating polio, eliminating measles, eliminating maternal and neonatal tetanus and achieving high and equitable vaccination coverage. With the global immunization strategy successor to the GVAP, the Immunization Agenda 2030 (IA2030), 122 million premature deaths are likely to be averted (WHO, 2020). For that, as MacDonald et al. (2020) argue, primary health centers must incorporate vital immunization programs with objectives that are sensitive to the situation and priorities of each country. Sriudomporn et al. (2022) pointed out that one of the objectives of IA2030 is to support a reliable global supply of vaccines and other immunization products of assured quality. However, planning mass vaccine campaigns is remarkably complicated, especially in rural communities of developing countries due to insufficient resources and low population density. Hospitals are scarce and spread apart, making the access to medical facilities and health-care treatments hard to achieve. Mainly due to distance and lack of nearby medical resources the citizens are rarely able to visit the nearest hospital to get vaccinated. Therefore, it is clear that there is a need to find good solutions to bring the health system closer to the rural area population. Attempting to answer the pressure of reaching everyone, it is more common for the health-care system to reach patients in their own location. Hence, to improve the situation, decision-makers could provisionally open several small vaccination centers spread throughout the rural region and schedule mobile units with professional health teams to cover the vaccination health needs.

In this context, an essential factor to take into account for health care in developing countries is the limitations of technology. These limitations, such as unstable internet connections, lack of updated information in real-time or obsolete workstations, make it necessary to develop tools that are simultaneously simple to understand, easy to use and that do not rely on advanced technology for their operation; otherwise, practitioners will not use the tools.

Motivated by a real-life problem faced by several nongovernmental health organizations during vaccination campaigns, the goal of this work is to model and solve a planning mass vaccination campaign problem (PMVCP) that aims to perform the vaccination campaign in the shortest possible term. Hence, the PMVCP combines four types of decisions, i.e. the location of the vaccination centers, the allocation of the population to the established vaccination centers, the schedule of the mobile work teams and the planning of routes. In that sense, we present a mathematical programming model to solve the PMVCP and propose a heuristic algorithm that is not only able to find quality solutions for the problem but can be embedded in a simple Excel spreadsheet-based tool (Hesse and Scerno, 2009). That way, the approach can be used by logistics planners providing, in short time, efficient solutions in a manageable way and allowing speeding up a planning process that even today is often done by hand based on the experience and intuition of the planner.

The remainder of this paper is structured as follows. In Section 2, we review the related literature. Section 3 describes the particular problem that we address, followed by the mathematical model. The proposed heuristic approach is then presented in Section 4. Section 5 reports the computational results. Finally, concluding remarks are presented in Section 6.

2. Related literature

We now review the relevant literature in health care in developing countries, with focus on planning vaccine campaigns and on the available tools. We position our contribution within this body of knowledge.

2.1 Health care in developing countries

Health-care logistics in developing countries need a broader perspective. Quality health-care services in remote areas are incredibly unaffordable for rural households. Although transport infrastructure may be available, there is spatial dispersion, poor road infrastructure and low supply due to a lack of resources. Furthermore, rural communities tend to be older and thus more likely to present medical conditions, placing them at higher risk (Arnaout and Arnaout, 2022). Quality health-care delivery is burdensome in terms of distance, time and affordability. Therefore, the mathematical models designed in the developed world context are often too sophisticated and need to consider new factors such as inadequate vehicles, road availability, variable weather conditions or mobile units.

Furthermore, like a vicious cycle, poverty in those regions leads to ill-health, and simultaneously, diseases affect individuals’ financial status through loss of income and increased susceptibility to catastrophic health-care costs (Chung et al., 2020). To break this vicious cycle, further improvements in the health-care system may depend on primary health care (PHC) service delivery. Gradually extending the PHC services to developing nations’ rural people may reduce morbidity and mortality and stimulate economic growth thanks to a healthier population. According to the Declaration of Alma-Ata (WHO, 1978), “primary health care is essential health care […] made universally accessible to individuals and families in the community through their full participation and at a cost that the community and country can afford […]”. PHC provides the means to deploy new vaccines and an expansion of vaccination programs that can substantively reduce childhood mortality in low- and middle-income countries. Hence, it is an essential part of the health system and contributes to social and economic growth. In fact, investigators from the Vaccine Impact Modeling Consortium estimated that vaccination against several pathogens (measles virus and others) averted approximately 37 million deaths from 2000 to 2019, representing a 45% decrease compared with a no-vaccination scenario, and an additional 32 million lives are projected to be saved from 2020 to 2030 (Sargent, 2021).

Several surveys review the applications of operation research in health care (Rais and Viana, 2010; Roy et al., 2020). However, we focus on developing tools to solve the problem that arises when planning vaccine campaigns. On their review about mass vaccination centers, Gianfredi et al. (2021) highlighted an important gap in knowledge and pointed out some of the aspects that should be considered in the planning, such as the identification of the locations, the role of the teams or the transportation aspect. In this sense, the present work considers the three aspects mentioned. On the one hand, decisions on the location of vaccination centers among potential ones are included. On the other hand, the role of the team is determined by providing the teams’ schedule during the campaign. Finally, transportation is considered in route design indirectly through travel time.

Geographical accessibility is essential for a good vaccination coverage. But public institutions or NGOs can rarely meet the associated costs of these resources in developing countries. That is why mobile health care units can be a great alternative, such as solutions provided by medical personnel with properly stored medicines that could travel among the settlements, providing medical services in more locations. The literature captures different applications and variants of mobile units, such as information and prevention, testing or application of treatments in a wide variety of medical services. Some examples of mobile units in health care are the ambulance routing, which is crucial in delivering emergency preparedness and response (Doerner and Hartl, 2008) or the blood sample collection problem, which aims to find the routes to collect blood samples from different locations and deliver them to a clinical laboratory for analysis (Grasas et al., 2014).

2.1.1 Planning vaccine campaigns

From the point of view of planning vaccine campaigns, the literature has been focused on studying the covering tour problem with the aim of minimizing travel distance or cost, as well as directly maximizing the coverage. Hodgson et al. (1998) proposed a model that minimizes a travel time of a mobile clinic, ensuring service to all population centers. Their formulation was tested on instances from Suhum District in Ghana, founding that 99% of the population can be served by a tour at a covering distance of 7 km. Doerner et al. (2007) considered two extra factors to optimize: minimizing the total distance traveled and maximizing population coverage. Lim et al. (2016) presented four models, differing in the type of coverage considered, to optimize the selection of outreach locations to maximize the population that can be reached. Lusiantoro et al. (2022) introduced a bi-objective mathematical location-allocation model based on a maximal covering location problem to determine the vaccination centers in developing countries by maximizing the demand coverage versus minimizing the traveled distance to access the service. Goentzel et al. (2023) proposed a mixed integer program that maximizes the immunization coverage within a budget and determines the location of outreach sites and the resource deployment across health-care centers. The authors applied their approach to a case study in Gambia, increasing coverage by about 6%.

In this paper, our goal is not only to determine the location and allocation of vaccination centers but also to determine the assignment of medical teams to vaccination centers while defining their time schedule and route. In terms of coverage, our study will guarantee a minimum percentage of coverage preestablished by the decision-maker. Furthermore, the critical aspect to optimize is the duration of the campaign without directly considering the distance traveled. Note that traveling long distances may result in lengthening the duration of the campaign.

2.2 Available tools

The vast majority of tools available for health care in developing countries are designed to support inventory management. Although there are also commercial software packages available to solve routing problems (such as BadgerMapping, OptimoRoute, Route4me or Routific), these require integration with existing software infrastructure, if any, as well as the need for the planning staff to learn how to use them. To the best of our knowledge, there are three optimization tools in the literature that overcome the problems of integrability and familiarity with the user by using Microsoft Excel software. Erdoğan (2017) uses a heuristic optimization algorithm integrated into Excel that solves many variants of the vehicle routing problem (VRP). In particular, the authors use visual basic for applications to code a variant of the adaptive large neighborhood search that allows them to obtain efficient solutions in a short computation time. Petroianu et al. (2020) developed a tool for routing and scheduling based on mixed integer programming to efficiently distribute vaccines and other medical supplies in Mozambique. The optimization algorithm to create the distribution routes and schedules is coded in Python in the background of an Excel file. De Armas et al. (2021) developed three module tools integrated in Microsoft Excel for helping the managers of assistive technology programs to make better logistics decisions. In particular, based on mathematical models and efficient algorithms, the modules have been developed to solve location, inventory and routing operational problems.

Nevertheless, these commercial software packages and optimization tools do not fit the needs and peculiarities of the PMVCP. For example, the possibility of having two teams working simultaneously or not at the same vaccination center means that vaccination centers can be visited from various routes, making decisions not only regarding the design of the route but also about the location of the vaccination centers and the corresponding allocation of population. Furthermore, unlike the usual practice, which is to minimize the total distance traveled and its associated cost, our tool focuses on minimizing the duration of the vaccination campaign to cover the population as soon as possible. Thus, the objective is to provide mass vaccination campaign planners with a tool that adapts to their specific needs through a simple and flexible tool based on Excel spreadsheets.

3. Problem description

Vaccination campaigns are one-off activities that are carried out as a preventive measure when the risk of an outbreak is high (for example, displaced population) or as a response when an outbreak has already been detected. The goal of vaccination campaigns is to immunize a large number of people in a short period of time. To this end, the setting up of multiple temporary vaccination centers with mobile medical teams is common.

The PMVCP consists of identifying optimal locations of vaccination centers, assigning population areas in need with demand to these locations in such a way that the inhabitants do not have to move more than a preset distance to reach the vaccination center and determining the work plan of the medical teams in terms of time and location. The PMVCP objective is to minimize the length of a mass vaccination campaign, considering certain requirements related to its operation.

From the point of view of the potential vaccination centers, their capacity is limited in terms of the maximum number of medical teams that can be working simultaneously. For each population area with demand, in addition to ensuring that citizens do not have to travel more than a preestablished distance to reach the assigned vaccination center, it is necessary to guarantee a minimum coverage percentage to satisfy, i.e. a minimum number of vaccines to dispense in each area. From the point of view of medical teams, they have a limitation in the daily workload, measured as the maximum number of daily vaccinations that they can dispense. Finally, from the point of view of route planning, each of the medical teams must start and end their route at the fixed central medical facility.

As mentioned above, the PMVCP combines four types of decisions: i) identifying where to locate the temporary vaccination centers, ii) allocating population areas in need with demand to these vaccination center, iii) the schedule-assignation of mobile medical work teams and iv) the route planning, with the aim of performing the vaccination campaign in the shortest possible time. Hence, the duration of a vaccination campaign will be determined by the number of days (effective work days plus travel days) necessary to achieve the established coverage. Therefore, the duration of the campaign will correspond to the length of the medical team with the longest schedule. Note that an optimal solution will simultaneously provide a balanced workload between the different medical teams since, by minimizing the temporarily longest route, all routes will tend to have similar lengths.

3.1 Mathematical programming formulation

Formally, the PMVCP is defined on a directed graph G = (V;A) in which a health-care system network is embedded, where V=v0,…,vn+1 is the vertex set and A is the arc set, |A|=m. We denoted by J⊂V the set of potential vaccination centers and by I⊂V the set of population areas in need with demand (not necessarily disjoint). We distinguish the fixed central medical facility by a double vertex, v0=vn+1. We define by O⊂A the set of arcs representing possible assignments of population areas with demand to potential vaccination centers {(i,j)| i∈I, j∈J} and by P⊂A the set of arcs representing the route of the medical team {(j,l)| j∈{v0}∪J, l∈J∪{vn+1}}. Furthermore, K denotes the set of medical teams.

We also define the following parameters and variables:

Parameters:

• b_i: demand at population area i∈I [vaccines];

• p:

  minimum coverage to consider a successful campaign [percentage];

• c_j: capacity of potential vaccination center j∈J [medical teams];

• d_ij: distance between population areas with demand i∈I and potential vaccination center j∈J, corresponding to assignment arcs (i,j)∈O [kilometers];

• Δ: maximum distance allowed between a population area with demand and its assigned vaccination center [kilometers];

• t_jl: traveling time between potential vaccination centers j, l∈J, corresponding to medical team route arcs (j,l)∈P [days]; and

• q^k: vaccination capacity of team k∈K [vaccines/day].

Variables:

• Y_j: binary variable equal to one if and only if potential vaccination center j∈J is opened [binary];

• X_ij: binary variable equal to one if and only if population area with demand i∈I is covered by vaccination center j∈J [binary];

• F_ij: coverage of population area with demand i∈I that is satisfied from a vaccination center located in j∈J [percentage];

• Rjk: binary variable equal to one if and only if team k∈K is assigned to vaccination center j∈J [binary];

• Wjlk: binary variable equal to one if and only if team k∈K goes from vaccination center j to vaccination center l for (j,l)∈P [binary];

• Zjk: number of working days team k∈K is assigned to vaccination center j∈J [days];

• Ujk: last day team k∈K is at vaccination center j∈J [days]; and

• V:

  length of the campaign [days].

The mixed integer linear program for the PMVCP is as follows:

(1) (PMVCP) minimize V

subject to:

(2) ∑j∈JFij≥p  i∈I

(3) Fij≤Yj  i∈I, j∈J

(4) ∑j∈JXij=1  i∈I

(5) dijXij≤Δ  (i,j)∈O

(6) Fij≤Xij  (i,j)∈O

(7) yj≤∑i∈IXij  j∈J

(8) ∑i∈IbiFij≤∑k∈KqkZjk  j∈J

(9) Zjk≤MRjk  k∈K, j∈J

(10) Rjk≤Zjk  k∈K, j∈J

(11) ∑k∈KRjk≤cjYj  j∈J

(12) Rjk≥Yj  k∈K, j∈J

(13) ∑j|(0,j)∈PW0jk=1  k∈K

(14) ∑l|(j,l)∈PWjlk=Rjk  j∈J, k∈K

(15) ∑l|(l,j)∈PWljk=∑l|(j,l)∈PWjlk  j∈J, k∈K

(16) ∑j|(j,n+1)∈PWjn+1k=1  k∈K

(17) Ujk+tjl+Zlk−Ulk≤M(1−Wjlk)  k∈K, (j,l)∈P

(18) U0k=0  k∈K

(19) V≥∑(j,l)∈Ptjlwjlk+∑j∈Jzjk  k∈K

(20) Yj∈{0,1}  j∈J

(21) Xij∈{0,1}  (i,j)∈O

(22) Fij∈[0,1]  (i,j)∈O

(23) Rjk∈{0,1}  k∈K, j∈J

(24) Wjlk∈{0,1}  (j,l)∈P, k∈K

(25) Zjk∈ℤ  k∈K, j∈J

(26) Ujk∈ℤ  j∈J∪0, k∈K

(27) V∈ℤ.  

The objective:

• (1): minimizes the total length of the campaign subject to the following constraints;

• (2): guarantee that at least a fixed percentage p of the demand is satisfied in each population area i∈I. Note that, currently the percentage of coverage required is the same in all population area. However, this percentage could easily differ for each of the population areas i∈I;

• (3): link the F and Y variables, ensuring that the demand is only satisfied from opened vaccination centers;

• (4): impose that each population area i∈I is assigned to only one vaccination center;

• (5): limit population areas with demand from being assigned to vaccination centers located within the maximum distance allowed;

• (6): link the variables F and X, ensuring that the demand is only satisfied from the assigned vaccination center;

• (7): link the Y and X variables, imposing that the only opened vaccination centers are those with assigned demand from some population area;

• (8): guarantee that the percentage of population covered from a vaccination center does not exceed the capacity of the teams assigned in that center;

• (9): link the variables Z and R, imposing that a medical team will have working days associated to a vaccination center only if it has been assigned to that center;

• (10): link the Z and R variables, ensuring that a medical team is not assigned to a vaccination center unless the medical team has working days at that center;

• (11): link variable R and Y variables, limiting the number of medical teams that can be assigned to a vaccination center according to its capacity;

• (12): link the R and Y variables, forcing not to open a vaccination center if there is no assigned medical team;

• (13): force the route of each medical team to start at the central medical facility, denoted by v₀;

• (14): link the variables W and R, guaranteeing that a medical team only leaves a vaccination center if the team has been assigned to it;

• (15): impose continuity of the medical team route, ensuring that if a medical team arrives at a vaccination center, it will also leave it;

• (16): force the route of each medical team to end at the central medical facility, denoted by vn+1;

• (17): keep track of the medical team’s route schedule (stating that if a medical team travels from vaccination center j to vaccination center l, it cannot leave l before the time the team left center j plus the time between centers plus the time spent at center l). In addition, prevent the formation of circuits;

• (18): ensure that each medical team leaves the central medical facility on day zero;

• (19): assign to variable V the duration of the campaign corresponding to the time of the medical team that has the longest scheduled route; and

• (20)–(27): domains of the decision variables.

4. Solution methodology

The big challenge here is to develop a solution approach that adequately represents the problem that arises in planning mass vaccination campaigns and provides efficient solutions that are also, easy to understand and use. In this sense, end users often do not have the necessary resources or time to run an optimization model and find the optimal solution, but instead need a good solution within minutes. Furthermore, simplicity is a key factor for organizations since most of the planning and/or daily operation tasks are carried out in many cases by volunteers with different training and background, with short periods of involvement or with a lot of staff turnover in the organization. For these reasons, we have decide to develop an heuristic approach that can be integrated in Microsoft Excel software.

In the following, we describe the heuristic approach we have developed to address the PMVCP. As previously mentioned, the PMVCP requires to take several decisions which are sequentially adopted in the proposed solution methodology. In that sense, we have developed a location-allocation first, route-scheduling second heuristic.

In the location-allocation phase, a constructive heuristic is applied to select the vaccination centers and assign the population areas to them. Then, in the route-schedule phase, for each medical team, the route and, indirectly, the schedule are obtained by applying a modification of the Clarke and Wright’s savings algorithm.

4.1 Location-allocation phase

The allocation of population areas with demand is determined by a probabilistic closest assignment within the preset distance limit. The first step in this phase is to initialize the method by opening all potential vaccination centers j∈J. Then, each demand area is allocated to the closest vaccination center with a preset probability of α or to the second closest with probability 1−α, always respecting the maximum distance allowed to travel, Δ. Frozen solutions can be prevented by modifying the value of α. After the assignation of all demand areas, we compute the aggregated demand at each vaccination center j∈J by summing up the demand of the population areas that have been previously allocated to it and close any vaccination center j∈J with zero aggregate demand.

4.2 Route-schedule phase

The aim of this phase is to design the route of medical teams and therefore also their schedule. To this end, we have used a modification of Clarke and Wright’s savings algorithm (see Section 4.2.1) to define the design of the route for each medical team k∈K. Note that when building the routes, the assignation of medical teams to population areas is inherent with the routes, as well as their schedules. In that sense, the schedule of the medical team is determined given the allocation of vaccination centers and their population areas with demand. Thus, it is possible to identify the working days each team k∈K has in the vaccination centers by dividing the aggregate demand at the vaccination center by the capacity of the team, q^k. To fully identify the schedule of each medical team, it is necessary to not only account for the working days in each vaccination center but also to add the necessary time between vaccination centers, corresponding to traveling and set-up time. Then, the day of arrival and departure to each vaccination center can be identified, considering the routes established and the fact that all medical teams start on day zero from the central medical facility. Finally, the duration of the vaccination campaign corresponds to the duration of the medical team with the longest schedule plan.

4.2.1 The Clarke and Wright’s savings modified algorithm

The Clarke and Wright

’s savings algorithm proposed in Clarke and Wright (1964) is the most known and widely used heuristic algorithm for solving the classical VRP, where a set of delivery routes must be established from a depot to various customers with demand to minimize the total distance traveled by the entire fleet. This algorithm is based on the basic concept of savings, understood as the distance savings obtained by joining two routes into a single route if no route constraint will be violated. So, the savings algorithm can be summarized in six simple, intuitive and easy-to-implement steps:

1. Create one route for each customer with demand c starting and ending at the depot 0, (0,c,0);

2. Compute the savings matrix for merging routes by calculating, for every pair of customers (i, j), sij=di0+d0j−dij where d_ij is the distances between customers i and j;

3. Order the savings in a nonincreasing list;

4. Starting from the top of the savings list, find the largest s_ij that satisfies:

   • i and j currently belong to different routes;

   • Both i and j are the first and the last customers in their respective routes; and

   • The sum of the demand of both routes is lower or equal to a preset amount, representing a capacity limitation on the vehicle;

5. Combine both routes by adding the arc (i, j) and removing the arcs (i,0) and (0,j); and

6. Repeat from step 4, until it is not possible to save more.

While in the classical VRP, the number of routes is initially unknown and will depend on the relationship between vehicle capacity and customer demand, in the PMVCP, the number of routes is known a priori, corresponding to the number of medical teams. Thus, following the same scheme, we use the concept of savings to merge routes until we obtain as many routes as the number of medical teams. Also note that in our adaptation of the algorithm, condition c) from step 4 does not apply since there is no capacity limitation on the vehicle. However, if the routes are built solely taking into account the minimization of the total distance, merging routes until obtaining one for each medical team, it is possible to obtain solutions that are inefficient for the PMVCP, such as the one shown in Figure 1 for three medical teams.

Although the three routes depicted in Figure 1 are well constructed, starting and ending at the central medical facility, from the point of view of our objective function, to minimize the duration of the vaccination campaigns, the solution obtained could be improved. In that sense, note that the three routes are completely different from each other in terms of the number of vaccination centers visited (represented by a circle with an inner cross). Thus, we find routes with a single vaccination center (in orange), with two centers (in green) or with four (in blue). In general, the fact of having such unbalanced routes implies that there will be routes much longer than others and therefore the duration of the vaccination campaign will be extended. For instance, within picture 1, the blue route will require more working days to serve all its vaccination centers assigned, which will therefore lengthen the total duration of the vaccination campaign.

A natural tactic to overcome this issue is to think about imposing a balance in the number of vaccination centers visited by each medical team. However, adding a condition whereby two routes could not join if the total number of vaccination centers at the junction exceeds the average number of vaccination centers per medical team continues to provide solutions that can be improved in terms of the longest route. In Figure 2, the routes have roughly the same number of vaccination centers, but if we consider the size of the circle as a proxy for the center’s aggregate demand, the routes are still unbalanced, to the detriment of the blue-colored route that serves the two vaccination centers with the highest demand. Therefore, a better approach is to limit the routes with the average demand, which is defined as the total demand divided by the number of teams, as shown in Figure 3. We can now see that the sum of the aggregated demands assigned to each of the routes is similar for all the teams, so the workload is distributed more equally among the teams regardless of the number of vaccination centers visited.

Therefore, to avoid overloaded routes and to balance the workload of the medical teams, we have added a new condition in step 4 of the Clarke and Wright’s savings algorithm, similar to a vehicle capacity limitation. For merging two routes, it must be verified that the new route will not exceed the average demand (see Appendix 2 for the details of the modified algorithm).

Note that to minimize the maximum length route, as stated in the model, it is equivalent to balancing the duration of the routes. If all routes have the same duration, then this will be the duration of the vaccination campaign. By balancing the workload of the teams, some routes are lengthened in both days and distance until no route is significantly longer in days. However, even though the routes to be merged are selected based on savings in distance traveled, the total distance traveled increases by balancing the workload. Although this is not a critical point in our study, since the objective of the PMVCP is to minimize the duration of the vaccination campaign and therefore the length in days of the longest route, even if this is detrimental to the total distance traveled.

4.3 Description of the tool integrated in Microsoft Excel software

As mentioned before, our heuristic approach is integrated in Microsoft Excel, which handles the input data, the heuristic resolution and the display of the solution, so that the user does not need more than basic Excel knowledge to execute and use the tool. In that sense, by opening the tool, the user will find an initial sheet to introduce the initial parameters of the problem (see Figure 4). By pressing the Start button, new sheets will be created based on the initial parameters to introduce further input data, such as coordinates or distances for population areas and vaccination centers, demands of population areas or vaccination centers and team capacities (see Appendix 3 for screenshot details). After adding all required input data, by pressing the Solve button, the proposed heuristic is applied and the solution is displayed.

5. Computational study

We now present the results of the computational study we have performed to analyze the performance of the proposed heuristic approach. In Section 5.1, we present a case study in Mozambique. Working with a real data can provide contextual understanding of our study. In Section 5.2, we analyze the performance of our heuristic approach in relation to the exact solution for large instances.

5.1 Case study: vaccination campaign in Mozambique

In this section, we aim to evaluate the proposed approach in real-world settings. For that, we will adapt the case study research proposed by Petroianu et al. (2020), which can be found on the referenced GitHub repository (Petroianu, 2020), licensed under the GNU General Public License v3.0. The Mozambique case study contains two data sets, named District A and District B, corresponding to information from two different Mozambican provinces. In particular, District A has 11 health centers, and District B has 16 health centers. We preserved from each setting the set of health centers that will be considered by us as the set of potential vaccination centers and the set of potential areas in need with demand, J = I, and the distance matrix between them. The central medical facility has been arbitrarily defined as the first vaccination center, and all vaccination centers can simultaneously accommodate two medical teams. At population areas we define the demand randomly distributed from an integer discrete uniform distribution U[100,500]. We consider two medical teams with a vaccination capacity of 100 vaccines per day each. Furthermore, from the scheduling point of view, we assume that the average traveling speed is 50 km/h and teams can travel for two hours (100 km) without affecting the ordinary course of the working day. Thus, if a medical team needs more than 2 h to move from one vaccination center to another, one additional day will be added to the length of the route. In this sense, district A, which has distances between 6 and 105 km, would only add one additional day in case of moving between a pair of vaccination centers (3, 9), while in the case of district B, the distances range between 6 and 177 km, and we find several pairs of vaccination centers more than 100 km apart. Therefore, for those pairs, it would be necessary to add an additional day to the route of the medical team.

5.1.1 Comparison and analysis of the schedule of medical teams

The schedule of the medical teams is decisive in determining the duration of the vaccination campaign, since this corresponds to the duration of the longest scheduled route. Figure 5 depicts for both districts the total days needed for each medical team by solving the model exactly and using the presented heuristic approach. The optimal solution has been found in both data sets through both resolution approaches. We can observe that the days needed in District A are 11 for both teams in both resolution approaches, and therefore the length of the vaccination campaign would be 11 days. In District B, the duration of the campaign would be 22 days, coinciding in both cases with the duration of the route of the team that needs more days. We can observe that team one is assigned 22 days by the two approaches, determining the total duration of the vaccination campaign. However, team two has a schedule of 22 days when solving the model to optimality and 17 days according to the heuristic approach.

In the case of District B, the solution obtained by our heuristic approach is an alternative optimal solution with total length of 22 days. The difference in the number of days needed by the medical team can be explained by three reasons: coverage percentage, distance and aggregated demand. On the one hand, our heuristic approach ensures exactly the minimum coverage percentage, p, in each population area with demand, while the mathematical model ensures that at least a percentage p is covered. In that sense, once the longest route can no longer be reduced, the duration of the rest of the routes can take any value as long as they ensure minimum coverage and do not exceed the length of the longest. Hence, the solution provided by the mathematical model for team two has some population areas vaccinated in a greater proportion since keeping the team in the vaccination centers for more days means providing greater coverage. On the other hand, distance together with aggregate demand can also be decisive to obtain alternative solutions. In that sense, although a team may have days available with respect to the longest route, it is possible that due to the demand associated with the vaccination centers, it may not be possible to reassign a vaccination center from the longest route to the free team without exceeding the initial duration of the longest route. Likewise, it is possible that given the aggregate demand and the distance between vaccination centers, it may not be possible to collaborate in serving one or more vaccination centers to reduce the duration of the longest route. The reader must remember that when vaccination centers are more than 100 km away from each other, extra days must be added.

5.1.2 Comparison and analysis of the vaccination centers

The solutions obtained use two or seven vaccination centers in District A and six or 11 vaccination centers in District B for the exact and heuristic approaches, respectively. Figure 6 presents the number of vaccination centers visited for each team in each solution for both data sets. It can be seen how the heuristic resolution provides a greater number of vaccination centers. This is due to the fact that the assignments of the population areas with demand are made to the closest center or the second closest according to a preset probability, and the fact that the closest center is always the population area itself (sets J = I).

Note that for the solutions obtained by exactly solving the mathematical model, the sum of the centers visited by both teams is greater than the number of opened vaccination centers. This is because some vaccination centers are visited simultaneously by both teams, as can be seen in Figure 7 for District A, where the working days that each team spends at the vaccination center are indicated in parentheses. Thus, it can be observed how team two (represented in green) visits only the vaccination center with the highest demand (represented by its size) spending 11 days, and that team one (represented in blue) initially visits for two days the same vaccination center and later visits the second vaccination for 9 days.

5.2 Scalability of the heuristic

Below, we present the results of some tests carried out to analyze the scalability of the heuristic with large instances. The sets of instances used in the computational experiments were randomly created. Table 1 shows the characteristics of the instances. The column headings represent the number of instances in the set (# of instances), the number of medical teams ( |K|), the number of potential vaccination centers ( |J|) and the number of population areas with demand ( |I|). Potential vaccination centers and population areas are randomly distributed in a 100 km side square. In population areas, we define the demand as being randomly distributed from an integer discrete uniform distribution U[50,250], with a minimum coverage percentage of p  =  0.9. In vaccination centers, we assume that all the locations could host all medical teams, and we consider two, four, six or eight medical teams with a vaccination capacity of 100 vaccines per day each.

Table 2 shows the aggregated results obtained for each group of instances, with the resolution of the presented mathematical model (within a 1-h limit time) and with our proposed heuristic approach. Columns # Opt and Gap report the number of instances in the group that were optimally solved and the average gap with respect to the optimal or best known solution, measured as the difference in days. Finally, the columns CPU give the average of the total computing times in seconds.

We can observe that the optimality of the solution was proven only for seven instances. Note that we were able to find the optimal solution for an instance in group R2-II and prove optimality by comparison with the best solution founded with the mathematical model. Although the heuristic provides slightly longer vaccination campaigns, it is able to offer quality solutions in a few seconds. In that sense, our heuristic approach is faster than solving the mathematical model, while the length of the campaign increases on average by less than two days with respect to the solution obtained by the model after 1 h. Furthermore, taking into account that the average duration of the campaign for all instances is 66 days, the average two-day difference is despicable in front of the benefit of a reduced computation time.

6. Conclusions

We have studied the PMVCP, which jointly tackles location, allocation, scheduling and routing decisions. We have presented a mixed integer linear model and proposed an heuristic approach that has been integrated in an Excel spreadsheet. As the numerical experiments show, our proposed heuristic provides good solutions in a short time, allowing us to provide a better service to the inhabitants and to reduce the length of the vaccination campaigns. Moreover, the results outperform those obtained by the mathematical model when analyzing the scalability of our heuristic approach. Due to its simplicity and flexibility, the proposed approach allows decision-makers to analyze and evaluate several possible scenarios for decision-making by simply playing with input parameters, resulting in a useful tool for practitioners. Furthermore, the integration of the heuristic approach in an Excel spreadsheet avoids the need for large investments in information systems infrastructure by user organizations.

Figures

Figure 1

Solution of the modified Clarke and Wright’s savings algorithm considering only maximum savings

Figure 2

Solution of the modified Clarke and Wright’s savings algorithm with balance in the number of centers per route

Figure 3

Solution of the modified Clarke and Wright’s savings algorithm with balance in the workload per route

Figure 4

Screenshot of basic initial parameters

Figure 5

Length in days of the routes per team in District A (left) and B (right)

Figure 6

Number of vaccination centers visited per team in District A (left) and B (right)

Figure 7

Solution obtained for District A by solving the mathematical model

Figure A1

Screenshot of distance input

Figure A2

Screenshot of demand parameters

Figure A3

Screenshot of capacity parameters

Table 1

Characteristics of the instances

Name group of instances	of instances	|K|	|J|	|I|
R2-I	5	2	25	100
R2-II	5		50	200
R4-I	5	4	25	100
R4-II	5		50	200
R6-II	5	6	50	200
R8-II	5	8	50	200

Source:

Authors’ own creation

Table 2

Computational results

	Mathematical model			Our heuristic
Name group of instances of instances	#Opt	Gap	CPU	#Opt	Gap	CPU
R2-I	5/5	0	541.58	0/5	3.8	0.47
R2-II	0/5	2	3,600	1/5	3	4.03
R4-I	1/5	0.8	2,997.45	0/5	2.6	0.56
R4-II	0/0	2	3,600	0/5	3.6	4.28
R6-II	0/5	1.8	3,600	0/5	3.6	4.80
R8-II	0/5	1.6	3,600	0/5	2.4	3.70

Source:

Authors’ own creation

Note

1 Appendix A contains a glossary of the abbreviations used in this paper.

Appendix 1. Glossary of the abbreviations

• GVAP: global vaccine action plan.

• IA2030: Immunization Agenda 2030.

• PHC: primary health care.

• PMVCP: planning mass vaccination campaign problem.

• SDG: sustainable development goal.

• UNICEF: United Nations Children’s Emergency Fund.

• VRP: vehicle routing problem.

• WHO: World Health Organization.

Appendix 2. The Clarke and Wright’s savings modified algorithm

Appendix 3. Screenshots of the tool integrated inMicrosoft Excel software