Prepositioning inventory for disasters: a robust and equitable model

Abstract

Disaster responses are usually joint efforts between agencies of different sizes and specialties. Improving disaster response can be achieved by prepositioning relief items in the appropriate amount and at the appropriate locations. In this paper, we develop a multi-agency prepositioning model under uncertainty. In particular, we develop a model in which the prepositioning strategy developed by a major aid agency or a local government considers sharing resources with other aid agencies. The proposed model considers multiple relief item types, storage capacity, budgetary and equity constraints while integrating supplier selection, inventory and facility location decisions. Uncertainty is modeled using robust optimization. We provide a deterministic model as well as its robust counterpart where demand and link disruptions are considered uncertain. In addition, a heuristic approach for solving the uncapacitated deterministic version of the proposed model is provided. In order to evaluate the proposed model and heuristic, two computational experiments are presented. In the first experiment, we assess the quality of the robust solutions by simulating a number of realizations. In the second experiment, we test the performance of the heuristic compared to the optimal policy.

1 Introduction

Major natural disaster events, such as the Great East Japan Earthquake in 2011, hurricane Sandy in 2012, the Nepal earthquake in 2015 and Louisiana severe storms and flooding in 2016, certainly captured the media’s attention. However, there are many more disasters that occur and are not publicized; an average of 375 natural disasters were reported each year between 2008 and 2017 (International Federation of Red Cross and Red Crescent Societies (IFRC) 2018). According to the Center for Research on the Epidemiology of Disasters (CRED), in 2017 more than 9500 people were killed and 96 million were reported affected by natural disasters. In the same year, natural disasters cost $334 billion (Center for Research on the Epidemiology of Disasters (CRED) 2018). Some types of natural disasters, such as floods and hurricanes, are recurring and can be predicted within a reasonable time frame prior to their onset (International Federation of Red Cross and Red Crescent Societies (IFRC) 2015). This time window can be used for preparedness activities in order to mitigate the impact of the disaster. As noted by Galindo and Batta (2013a), a key part of the preparedness activities relates to the prepositioning of emergency supplies. Prepositioning strategies can improve response time in a post-disaster situation, which can save lives and reduce economic loss. Our research is focused on the prepositioning of supplies as a preparation strategy for such natural disasters.

In our model, demand for relief items at dispensing locations must be served; some of this demand is served by prepositioned supplies so that it is immediately available, while any remaining demand is served with supplies acquired post-disaster. Considering that our model determines the location, amount and distribution of relief items, it is important to incorporate equity into the decision process. An equitable solution will distribute prepositioned relief items proportionately to the demand in all dispensing locations. This means that in a perfectly equitable solution, the same fraction of demand is served at all dispensing locations using prepositioned relief items (versus supplies acquired post-disaster). Based on this definition of equity, we also define a level of tolerable inequity as the range between the maximum and the minimum fraction of prepositioned demand among all dispensing locations. By controlling the level of tolerable inequity, the modeler will be able to analyze the trade-offs between effectiveness and equity.

Inventory prepositioning models are difficult for humanitarian organizations to implement. First, inventory prepositioning models are becoming increasingly more sophisticated requiring high levels of expertise in order to be used in a real-world setting. Second, personnel in charge of humanitarian logistics activities usually lack formal education in humanitarian logistics (Crum et al. 2011). Third, humanitarian organizations lack adequate investment in technology including the use of methods such as mathematical modeling (Beamon and Kotleba 2006; Gustavsson 2003). Our approach aims to define a series of policies and condense them into a practical implementable heuristic. With this approach, we exploit the benefits of applying operations research methods such as mixed integer linear programming and robust optimization while making them accessible and implementable to people outside an academic environment. The fundamental idea is that the resulting policies of this work can be implemented by humanitarian organizations using their own personnel with no additional investment in external consulting or optimization software.

The proposed model considers a scenario in which a major aid agency or local government, acting as coordinator of a disaster response, must plan a prepositioning strategy considering a multi-agency effort. The major aid agency is considered to have a limited budget to allocate among inventory, warehousing and distribution. Affiliates collaborate by providing relief items and are allowed to use the facilities opened by the major aid agency. Affiliates’ supply distribution capabilities, or responsiveness, are captured by a parameter called “inefficiency”, which is used as a factor in the objective function. Our work shows that such supply distribution capabilities of the affiliates affect the coordinator’s budget allocation and, thus, must be taken into consideration. Henceforth, we refer to the decision maker (e.g., local government) as the coordinator and the affiliates (e.g., FEMA, NGOs) as outside sources.

In this paper, we propose deterministic and robust formulations with an accompanying heuristic approach in order to select suppliers, locate distribution centers and determine the amount of relief items to be stored in the selected distribution centers. The objective of our model is to minimize the total demand-weighted distance between distribution centers and dispensing locations. A limited budget used for opening distribution centers and procuring relief items is considered. Moreover, the solution must meet a predefined level of tolerable inequity. Agencies participating in the disaster response effort (i.e., affiliates) are incorporated into the model as outside sources. In a real setting, relief items that might come from an outside source can be a result of agreements within humanitarian organizations, inter-state agreements or federal aid.

The remainder of the paper is organized as follows: Section 2 provides a review of the literature which relates most closely to our problem. Section 3 presents a description of the problem we intend to solve and our assumptions, while Sect. 4 contains the model notation and mathematical formulations. Section 5 introduces the proposed heuristic. Section 6 is organized as follows: First, we describe the methodology to randomly generate the instances of the problem that were used in the computational experiments. Second, we present the computational experiments under nominal data and assess the robustness of the solutions under realizations. Third, we perform a sensitivity analysis on several parameters. Section 7 presents our conclusions and future research objectives.

2 Previous related work

According to Apte (2010), humanitarian logistics involves planning, implementation and decisions related to the flow and storage of goods and information in a humanitarian context. Van Wassenhove (2006) identifies four phases in a disaster cycle: mitigation, preparedness, response and rehabilitation. Inventory prepositioning, which takes place in the preparedness phase, is identified as consisting of facility location, inventory management and transportation decisions (Duran et al. 2011). In this section, we review the literature on inventory prepositioning. For comprehensive literature reviews on humanitarian logistics, see Altay and Green (2006); Galindo and Batta (2013b) and Caunhye et al. (2012).

We divide our review into optimization and heuristic approaches. The optimization approaches considered in this review fall into the following categories: deterministic, stochastic and robust models. Early models in inventory prepositioning were deterministic and based on well-known facility location problems such as set covering (Hale and Moberg 2005) and p-median (Akkihal 2006). Hale and Moberg (2005) determine the location of storage areas for critical emergency resources to efficiently serve multiple supply chain facilities. Akkihal (2006) identifies optimal locations for prepositioning non-consumable inventories by minimizing the average global distance from the nearest warehouse to a beneficiary.

Due to the complexity of humanitarian environments, uncertainty is usually considered in inventory prepositioning models. Stochastic programming is by far the most commonly used approach in inventory prepositioning. For a review of two-stage stochastic programming in disaster management, see Grass and Fischer (2016). In general, two-stage stochastic inventory prepositioning models consider location and amount prepositioned as first-stage decisions while transportation decisions are considered in the second-stage. Objective functions used in these studies include minimizing expected total cost (Chang et al. 2007; Rawls and Turnquist 2010; Mete and Zabinsky 2010; Döyen et al. 2012), maximizing satisfied demand (Balcik and Beamon 2008), minimizing average response time (Duran et al. 2011) and minimizing the number of casualties (Salmerón and Apte 2010). Stochastic programming models, such as the ones mentioned above, require the probability distribution of the uncertain parameters, which in many cases may be very difficult to obtain (Ben-Tal et al. 2011).

One of the standard methods used to model uncertainty is robust optimization. Robust optimization is a methodology which is concerned with finding solutions that perform well with respect to uncertain future conditions (Peng et al. 2011). For a comprehensive review on robust optimization, see Ben-Tal et al. (2009), Bertsimas et al. (2011) and Gabrel et al. (2014). Robust optimization is particularly useful in situations where it is very difficult to identify probability distributions to model the uncertain data (Ben-Tal et al. 2011). The complexity and unique characteristics of each disaster response setting make inventory prepositioning a suitable candidate to exploit the benefits of robust optimization, which is the approach used in this paper.

Robust optimization approaches have been used in humanitarian logistics. However, only a few papers have studied robust optimization approaches in inventory prepositioning. Zokaee et al. (2016) propose a single-stage robust optimization model that minimizes a relief chain’s total costs while ensuring a minimum percentage of demand satisfied for all affected areas. They consider uncertainty in demand supply and cost parameters. Instead, we focus on uncertainty in demand and link disruptions. Ni et al. (2018) propose a two-stage robust optimization model that minimizes logistics and deprivation costs for a single type of relief supply. We propose a multi-commodity single-stage robust optimization model. Furthermore, our work differs from these studies due to (i) the definition of the objective function (our model minimizes total demand-weighted distance) and (ii) the focus on considering a coordinated multi-agency disaster response.

Another aspect in which our work diverges from previous studies related to inventory prepositioning is our interest in developing heuristic approaches. Two common characteristics can be found in heuristics proposed in the humanitarian context. First, these heuristics are usually employed in conjunction with an optimization model (Yi and Özdamar 2007; Rath and Gutjahr 2014 and Galindo and Batta 2013a). Yi and Özdamar (2007) propose a two-phase location-distribution model where, in the first phase, location decisions are taken using a mixed integer optimization model and, in the second phase, a heuristic is employed to determine routing decisions. Rath and Gutjahr (2014) solve a three-objective model considering location and routing decisions where constraints are heuristically generated and added in each iteration. Galindo and Batta (2013a) propose a heuristic approach for clustering locations allowing the optimization model to solve larger instances. Second, the majority of the proposed heuristics are usually employed to determine transportation and routing decisions. Berkoune et al. (2012) develop a genetic algorithm to solve disaster relief transportation problems. Ferrer et al. (2016) propose a multi-criteria model to determine a distribution plan for relief aid in disaster response. To the best knowledge of the authors, there are no papers proposing heuristics for inventory prepositioning that are not optimization-based and consider facility and inventory decisions. One of the contributions of our paper is that we develop a greedy heuristic with budgetary and equity constraints.

Equitable or fair distribution of relief supplies is an important aspect in inventory prepositioning. Only a few papers in inventory prepositioning consider equity or fairness. Bozorgi-Amiri et al. (2013) incorporate fairness as one of two objectives by minimizing the maximum shortage of relief items at the dispensing locations. Rezaei-Malek and Tavakkoli-Moghaddam (2014) incorporate a fairness level into the model where the difference of weighted unsatisfied demands between two demand points does not exceed a maximum considered amount of fairness level defined by experts. Zokaee et al. (2016) consider equity by creating a new constraint ensuring that a predefined minimum percentage of relief items demand must be satisfied. Similar to Zokaee et al. (2016), we consider the level of tolerable inequity, which is the range of fraction of demand satisfied by prepositioned supplies, as a parameter that is specified by the user.

Literature on inventory prepositioning models considering cooperation among multiple relief agencies is limited. Although disaster responses usually require the intervention of many organizations (Akhtar et al. 2012), the vast majority of inventory models in the literature consider one agency. Furthermore, most of the papers study coordination in the humanitarian context from a conceptual perspective (Balcik et al. 2010; Feng et al. 2010; Akhtar et al. 2012). In this paper, we propose a robust optimization model for inventory prepositioning considering agency cooperation in the form of relief aid available post-disaster.

The interaction and relationships among these different actors participating in the relief effort are known as coordination (Balcik et al. 2010). Cooperation mechanisms used pre-disaster including logistics decisions such as procurement, warehousing and transportation (Balcik et al. 2010). Our proposed model focuses on the warehousing decisions. In particular, we are concerned with the location and capacities of storage facilities that are shared by several aid agencies. This coordination strategy for warehousing facilities has low associated costs, low technological requirements and high potential for implementation (Feng et al. 2010). Furthermore, adequate storage facilities required during a relief effort might be difficult to find (Balcik et al. 2010; Akhtar et al. 2012).

A review of the literature reveals gaps in humanitarian logistics research. The main contributions of our work are as follows: First, we extend the literature in humanitarian logistics by developing a robust inventory prepositioning model that can be used in a multi-agency disaster response. Furthermore, we develop a heuristic approach for the uncapacitated deterministic version of our model that could be used in environments where costly barriers to use off-the-shelf optimization software, such as training or licensing, are present. Second, we extend the literature in robust optimization by applying Bertsimas and Sim (2004) budget uncertainty model to an inventory prepositioning problem under demand and network damage uncertainty.

3 Problem description and assumptions

Let us assume that a hurricane is expected to make landfall in the upcoming days. A local government or major aid agency, i.e., the coordinator, has decided to plan a prepositioning strategy in collaboration with other humanitarian organizations, i.e., outside sources. We hypothesize that outside sources capabilities affect the coordinator’s prepositioning strategy in terms of the location and amount of prepositioned relief supplies. Therefore, the coordinator must consider outside sources in the decision process in order to improve the overall disaster response. Examples of relief items to be prepositioned include water, ready-to-eat meals, comfort and medical kits. An area that contains the population that could potentially be affected by a disaster is determined and a forecast of demand for relief items has been generated. In addition, based on this preliminary assessment of demand quantity and location, a set of potential distribution center locations and a set of suppliers are defined.

Fig. 1

Schema of the proposed disaster relief chain. Solid lines represent relief item flows from distribution centers to dispensing locations. Dashed lines represent flow from suppliers to distribution centers. Dashed dotted lines represent flows from outside sources to distribution centers

In this paper, we study a single-period three-level multi-commodity disaster relief chain. As shown in Fig. 1, the first level of our relief chain consists of suppliers and outside sources, the second level contains distribution centers, and the last level is the set of dispensing locations. Relief items provided by the coordinator are procured pre-disaster from suppliers and prepositioned at the distribution centers. In the same level of the suppliers, outside sources procure relief items post-disaster and use distribution centers to serve the dispensing locations. In the second level, distribution centers have finite capacities to store prepositioned relief items. Dispensing locations, the last level, represent the areas where relief items are received by the affected population.

The proposed model determines the flow of relief items through the considered disaster relief chain and the location of the distribution centers in an effective and equitable manner. To this aim, two models are proposed: a deterministic model (Sect. 4.2) and its robust counterpart (Sect. 4.3) where demand and link disruptions are considered uncertain. The main assumptions in our deterministic model are summarized as follows, while relaxations of these assumptions are explained when the robust model is introduced:

• 1. Costs and distances are known.

• 2. Facilities have known storage capacity and are not affected by the disaster.

• 3. Demand for relief items is deterministic and known (relaxed in the robust formulation).

• 4. Links are not affected by the disaster (relaxed in the robust formulation).

Deterministic models imply that all parameters used, such as demand, costs and distances, are known and fixed. For instance, prior to the use of the proposed model, demand might be forecasted based on historical data and procurement and transportation costs might be determined and agreed upon with suppliers. Distances between locations are also assumed to be known and remain fixed post-disaster which means that if a route is disrupted, another route of the same characteristics can be used. These types of assumptions, such as assumptions 1 and 2, are also found in (Verma and Gaukler 2015) and (Galindo and Batta 2013a).

Fig. 2

Tropical cyclone storm surge (left) and flood hazard (right) maps for Coastal North Carolina

Distribution centers are desired to be located near the dispensing locations. However, as they are carefully chosen prior to the disaster, they are not located in disaster-prone areas and have the necessary infrastructure to remain operational post-disaster (Dr. J. Casani, personal interview). There are available data regarding hazards that might put the operation of an opened distribution center at risk. For instance, Fig. 2 shows the results of two different risks in coastal North Carolina: The left figure shows the areas where the water level would increase due to the presence of a category-5 tropical cyclone. The map on the right shows the flood risk caused by rain. The sources of the risk maps shown above come from official sites such as the National Hurricane Center (www.nhc.noaa.gov) and the Government of the State of North Carolina (www.nc.gov).

In our robust optimization model, we relax the third and fourth assumption by considering demand and link disruptions uncertain. As noted by Mert and Adivar (2010), in real humanitarian operations, sources of uncertainty are various. Factors such as the demand, availability and cost associated with the procurement and distribution of relief items are uncertain. Thus, we focus on demand and link disruption uncertainty and discuss potential extensions to include other sources of uncertainty.

4 Mathematical formulation

We propose a model that minimizes the total demand-weighted distance between distribution centers and dispensing locations subject to budget and equity constraints where demand may be satisfied partially by the coordinator and outside sources. The coordinator manages the available budget for the prepositioning strategy, i.e., cost of opening distribution centers and prepositioned relief items. The outside sources, which can also provide relief supplies, use the distribution centers opened by the coordinator to serve the dispensing locations.

In this section, we first discuss key aspects of our models, such as equity, outsource efficiency and costs. Then, we introduce two inventory prepositioning models. The first model is deterministic and the second is a robust optimization model where we assume uncertainty in demand for relief items and link disruptions.

4.1 Definitions

In this section, we discuss three key definitions of our proposed model. First, we define equity and describe how it is modeled. Second, we discuss the outside source efficiency and how it is incorporated into our models. Finally, we examine how the cost parameters used in the models might be calculated.

4.1.1 The trade-off between effectiveness and equity

In our model, effectiveness is measured as the total demand-weighted distance between distribution centers and dispensing locations and equity is calculated based on the fraction of demand that is served with prepositioned relief items. In order to illustrate the effectiveness-equity trade-off, let us assume a network with one distribution center and two demand locations located at 10 and 20 units of distance away, as shown in Fig. 3. In addition, assume that each demand location, A and B, requires 100 units of relief items, and we are allowed to distribute only 100 units of relief items in total. If we want to provide a perfectly equitable solution (i.e., level of inequity = 0), we must distribute $50\%$ of demand to both locations, resulting in a total demand-weighted distance of $0.5\times 100\times 10 + 0.5\times 100\times 20 = 1500$. Now suppose we define a level of tolerable inequity of 0.2. In this case, we can send more items to the closer dispensing location resulting in a reduction in the total demand-weighted distance of $0.6\times 100\times 10 + 0.4\times 100\times 20 = 1400$. With this illustration, we can see that we can improve our demand-weighted total distance by increasing the level of tolerable inequity.

Fig. 3

A distribution center (shaded triangle) serving dispensing locations A and B located at 10 and 20 units of distance, respectively. Demand for relief items required to be served is 100 units at both dispensing locations A and B

4.1.2 Outside sources and their efficiencies

Recall that the coordinator’s inventory is prepositioned, while aid from outside sources is shipped to the distribution centers post-disaster. Parameter f is an inefficiency factor or a penalty associated with not having supply immediately available. Inefficiencies can occur for multiple reasons including higher procurement costs, longer travel distances, delays in transport and reduced transportation capacity. Next we show one way to estimate parameter f considering inefficiencies related to transportation capacity.

Since outside sources may vary in size and expertise, a reasonable assumption to make is that their efficiency—or inefficiency—in disaster response might vary as well. For modeling purposes, inefficiency is expressed with the parameter f. Here, let the inefficiency factor f be a unit-less ratio between the aggregated response rate of all outside sources and the coordinator’s response rate. Response rates $\Delta _i$ are defined as the speed at which demand can be served by agency i. One suggestion for the calculation of parameter f is as follows:

$$\begin{aligned} f = \frac{\Delta _c}{\sum _{s \in {\mathcal {S}}} \Delta _s} \end{aligned}$$

(1)

where

$$\begin{aligned} \Delta _i = \Big ( \frac{nq}{t} \Big )_{i}. \end{aligned}$$

(2)

Equation (2) is used to calculate response rates for the coordinator (i.e., $i=c$) and the outsides sources (i.e., $i=s, s \in {\mathcal {S}}$). Assuming that each affiliate’s fleet is homogeneous, n is the number of trucks and q is the capacity of each truck. Finally, t is the sum of minimum travel times that affiliate i requires to reach all dispensing locations.

If the inefficiency factor $f > 1$, this means that the affiliate is more inefficient than the coordinator in responding to the disaster. On the other hand, if the inefficiency factor $f < 1$, the affiliate is less inefficient than the coordinator in responding to a disaster. Once the disaster occurs and the disaster response begins, outside sources must ship relief items to the distribution centers before they are sent to the dispensing locations, while the coordinator’s inventory is already prepositioned at the distribution centers. Therefore, a reasonable assumption to make regarding the outside source inefficiency factor is that $f > 1$. The above is meant to illustrate one way to estimate f; ultimately, this serves as a penalty associated with not having relief items immediately available which can cause human suffering.

4.1.3 Cost parameters

Our model considers three types of cost. Cost parameter $c^1$ includes transportation cost from suppliers to distribution center and procurement cost, cost parameter $c^2$ represents the transportation cost from the distribution centers to the dispensing locations, and cost parameter $c^3$ represents the cost of setting up a distribution center. A finite budget for prepositioning is assumed to be available. Cost parameters are only associated with the coordinator since it is the entity that manages the available budget for disaster response.

4.2 Deterministic model

Table 1 contains the notation used in our proposed models. The deterministic formulation is as follows:

$$\begin{aligned}&\text {Minimize } \sum _{j,k,l} d_{jk} v_{kl} y_{jkl} + f \cdot \sum _{j, k,l} d_{jk} v_{kl} w_{jkl} \end{aligned}$$

(3)

$$\begin{aligned}&\text {subject to } \sum _{i,j,l} c^{1}_{ijl} x_{ijl} + \sum _{j,k,l} c^{2}_{jkl} v_{kl} y_{jkl} + \sum _{j} c^{3}_{j} z_{j} \le b, \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{k} v_{kl} y_{jkl} \le \sum _{i} x_{ijl} \qquad \forall \, j,\,l, \end{aligned}$$

(5)

$$\begin{aligned}&\sum _{k,l} v_{kl}y_{jkl} \le K_{j}z_{j} \qquad \forall \, j,\end{aligned}$$

(6)

$$\begin{aligned}&\sum _{k} w_{jkl} \le Mz_{j} \qquad \forall \, j,\,l,\end{aligned}$$

(7)

$$\begin{aligned}&\gamma \le \sum _{j} y_{jkl} \le \theta \qquad \forall \, k,\,l, \end{aligned}$$

(8)

$$\begin{aligned}&\theta - \gamma \le \alpha , \qquad \end{aligned}$$

(9)

$$\begin{aligned}&\sum _{j} y_{jkl} + \sum _{j} w_{jkl} \ge 1 \qquad \forall \, k,\,l,\end{aligned}$$

(10)

$$\begin{aligned}&y_{jkl} + w_{jkl} \le 1 - u_{k} \qquad \forall \,j, \,k,\,l,\end{aligned}$$

(11)

$$\begin{aligned}&z_{j} = \{0, 1\} \qquad x_{ijl},\; y_{jkl},\; w_{jkl},\; \theta ,\; \gamma \ge 0 \qquad \forall \,i,\,j,\,k,\,l. \end{aligned}$$

(12)

Table 1 Definitions of sets, indexes, decision variables and parameters used in the proposed models

The objective function (3) minimizes the total demand-weighted distance from distribution centers to dispensing locations. In Eq. (3), the first term represents the sum of demand-weighted distances of demand served with relief items prepositioned by the coordinator, while the second term represents the sum of demand-weighted distances of demand served with relief items provided by the outside sources. Equation (4) expresses the coordinator’s budget constraint. Equation (5) guarantees that relief items delivered by the coordinator to dispensing locations are available at distribution centers. Equation (6) ensures that capacities to store prepositioned relief items at distribution centers are respected. Equation (7) ensures that outsides sources use only opened distribution centers. Equity is modeled by Eqs. (8) and (9). Equation (8) serves the purpose of assigning the maximum and minimum fraction of demand served by the coordinator (i.e., using prepositioned relief items) to auxiliary variables $\gamma$ and $\theta$, while Eq. (9) ensures that the range between the auxiliary variables $\gamma$ and $\theta$ is less or equal than the parameter $\alpha$. Equation (10) guarantees that all demand must be met. Equation (11) limits link capacities. Equation (12) represents the binary and non-negativity constraints.

4.3 The robust model

In this section, we introduce the robust counterpart where demand and link disruptions are assumed uncertain. Demand uncertainty is modeled using the budget uncertainty set approach proposed by Bertsimas and Sim (2004). Some of the advantages of using the uncertainty budget model are (i) the robust formulation maintains the complexity of its deterministic counterpart and (ii) the modeler can control the level of conservativeness in the solution. Uncertainty in link disruption is modeled using the interval uncertainty set proposed by Soyster (1973).

Let us define demand ${\tilde{v}}_{kl}$ as the uncertain parameter where each ${\tilde{v}}_{kl}$ is modeled as a symmetric and bounded random variable that takes values in $[v_{kl} - {\hat{v}}_{kl}, v_{kl} + {\hat{v}}_{kl}]$. Parameter $v_{kl}$ represents the demand nominal value, and the perturbation ${\hat{v}}_{kl}$ is computed as ${\hat{v}}_{kl} = \epsilon {v}_{kl}$ where $\epsilon$ is referred to as the demand variability. The budget uncertainty set approach proposed by Bertsimas and Sim (2004) allows the modeler to control the level of protection against uncertainty by defining a parameter named $\Gamma$, which determines the number of uncertain parameters that are allowed to vary.

Following Bertsimas and Sim (2004), the standard procedure to develop the robust reformulation of a linear problem is that we first introduce the protection function in those constraints affected by the uncertain parameter ${\tilde{v}}_{kl}$. Then, we rewrite the added protection function in the form of an optimization problem. Finally, the protection function in the form of an optimization problem is substituted by its dual. Let us illustrate this procedure with the deterministic objective function (Eq. 3).

The robust counterpart of the deterministic objective function (Eq. 3) can be written as

$$\begin{aligned} \text {Min } \sum _{j,k,l} v_{kl} {\chi _{jkl}} + \beta ({\chi _{jkl}}, \Gamma ) \end{aligned}$$

(13)

where ${\chi _{jkl}} = d_{jk} (y_{jkl} + f w_{jkl})$ and $\beta ({\chi _{jkl}}, \Gamma )$ is defined as the protection function.

Given ${\chi ^{*}_{jkl}}$ and assuming that protection levels ($\Gamma s$) only take integer values, the protection function can be written as

$$\begin{aligned} \beta ({\chi ^{*}_{jkl}}, \Gamma ) = \max _{\{S | S \subset V, |S| \le \Gamma \}} \bigg \{ \sum _{(k,l) \in S} {\hat{v}}_{kl} \sum _j {|\chi ^{*}_{jkl}|} \bigg \} \end{aligned}$$

(14)

where $V = \{ (k,l) | {\hat{v}}_{kl} > 0\}$, $\Gamma \in [0, |S|]$ and S represents the set of uncertain parameters.

As the procedure indicates, the above formula is written as a linear optimization problem:

$$\begin{aligned} \begin{aligned} \text {maximize }&\sum _{(k,l) \in V} {\hat{v}}_{kl} p_{kl} \sum _j {|\chi _{jkl}|} \\ \text {subject to }&\sum _{(k,l) \in V} p_{kl} \le \Gamma \\&0 \le p_{kl} \le 1, \quad \forall (k,l) \in V\\ \end{aligned} \end{aligned}$$

(15)

and the dual can be written as

$$\begin{aligned} \begin{aligned} \text {minimize }&\quad \sum _{(k,l) \in V} \mu _{kl} + \lambda \Gamma \\ \text {subject to }&\quad \lambda + \mu _{kl} \ge {\hat{v}}_{kl} \gamma _{kl}&\forall (k,l) \in V\\&-\gamma _{kl} \le \sum _j {\chi _{jkl}} \le \gamma _{kl}&\forall (k,l) \in V\\&\quad \lambda , \mu _{kl}, \gamma _{kl} \ge 0&\forall (k,l) \in V\\ \end{aligned} \end{aligned}$$

(16)

where $\lambda$, $\mu _{ kl}$ and $\gamma _{kl}$ are dual variables.

We have shown the steps needed to reformulate the objective function. By repeating these steps with the budget, balance and storage capacity constraints, i.e., Eqs. (4)–(6), the robust linear problem with uncertain demand can be written as follows:

$$\begin{aligned}&\text {Minimize } \sum _{j,k,l} v_{kl} {\chi _{jkl}} + \lambda \Gamma + \sum _{(k,l) \in V} \mu _{kl} \end{aligned}$$

(17)

$$\begin{aligned}&\text {subject to } \sum _{i,j,l} c^{1}_{ijl} x_{ijl} + \sum _{j,k,l} c^{2}_{jkl} v_{kl} y_{jkl} + \sum _{j} c^{3}_{j} z_{j} + \lambda \Gamma + \sum _{(k,l) \in V} \mu _{kl}\le b, \end{aligned}$$

(18)

$$\begin{aligned}&\sum _{k} v_{kl} y_{jkl} + \lambda \Gamma + \sum _{k \in V} \mu _{kl} \le \sum _{i} x_{ijl} \qquad \forall j, l, \end{aligned}$$

(19)

$$\begin{aligned}&\sum _{k,l} v_{kl}y_{jkl} + \lambda \Gamma + \sum _{(k,l) \in V} \mu _{kl} \le K_{j}z_{j} \qquad \forall \, j,\end{aligned}$$

(20)

$$\begin{aligned}&\lambda + \mu _{kl} \ge {\hat{v}}_{kl} \gamma _{kl} \qquad \forall (k,l) \in V,\end{aligned}$$

(21)

$$\begin{aligned}&-\gamma _{kl} \le \sum _j {\chi _{jkl}} \le \gamma _{kl} \qquad \forall (k,l) \in V,\end{aligned}$$

(22)

$$\begin{aligned}&-\gamma _{kl} \le \sum _j c^{2}_{jkl} y_{jkl} \le \gamma _{kl} \qquad \forall (k,l) \in V,\end{aligned}$$

(23)

$$\begin{aligned}&-\gamma _{kl} \le \sum _{j,l} y_{jkl} \le \gamma _{kl} \qquad \forall (k,l) \in V,\end{aligned}$$

(24)

$$\begin{aligned}&-\gamma _{kl} \le \sum _{j} y_{jkl} \le \gamma _{kl} \qquad \forall (k,l) \in V,\end{aligned}$$

(25)

$$\begin{aligned}&\lambda , \mu _{kl}, \gamma _{kl} \ge 0, \qquad \forall (k,l) \in V,\end{aligned}$$

(26)

$$\begin{aligned}&\text {Constraints (8)--(12).} \end{aligned}$$

(27)

Equation (17) represents the robust form of the objective function, i.e., Eq. (3). Similarly, Eqs. (18)–(20) are the robust form of Eqs. (4)–(6). Equations. (21)–(26) represent the constraints of the protection functions written in dual form, as shown in Problem 16.

In order to incorporate uncertainty in link disruptions, let us assume that capacity can be reduced by an uncertain value of ${\tilde{u}}_{k}$ in those links connecting dispensing locations k that belong to set ${\mathcal {L}}$. Uncertain parameters ${\tilde{u}}_{k}$ are assumed to be independently distributed and can take any value in the range $[{u}_{k}, {\hat{u}}_{k}]$. The nominal value ${u}_{k}$ is assumed to take the value of 0, which means that there is no link disruption.

Link capacity reduction ${\hat{u}}_{k}$ takes a value between 0 and 1, where 0 means that the link is undamaged and 1 means that the link is broken. Given that the uncertain parameter ${\tilde{u}}_{k}$ will take the value of ${\hat{u}}_{k}$ in the worst-case scenario, a robust solution with respect to link disruption is found if we replace ${\tilde{u}}_{k}$ by ${\hat{u}}_{k}$ in those links connecting distribution centers to dispensing locations that belong to a predefined set ${\mathcal {L}}$.

In order to consider link disruptions uncertain in the robust model (17)–(27), we replace constraint (11) with

$$\begin{aligned} \sum _j y_{jkl} + \sum _j w_{jkl} \le 1 - {\hat{u}}_{kl} \qquad \forall \, (k,l) \in {\mathcal {L}}. \end{aligned}$$

(28)

5 A greedy heuristic

In this section, we develop a greedy heuristic for solving the uncapacitated deterministic version of the proposed model. We base our algorithm on the dropping heuristic originally proposed by Kuehn and Hamburger (1963) with the following key differences. First, we use a $p-$median objective function where we minimize the total demand-weighted distance between distributions centers (DCs) and dispensing locations. Second, we add budgetary constraints in a similar fashion as proposed by Wang et al. (2003). Finally, we introduce additional steps to ensure equity constraints are met.

The algorithm consists of the main heuristic, i.e., the equitable inventory prepositioning heuristic, and a subprocedure, i.e., the budget reallocation heuristic. Our proposed algorithm begins by choosing which distribution centers (DCs) to open and a fraction $\delta$ of prepositioned demand for all dispensing locations (DLs) and relief items considering that all DCs are available. This is considered as the initial solution. Then, by using a cost-to-benefit ratio as a criterion, DCs are iteratively closed until no further improvement in the objective value is achieved.

The equitable inventory prepositioning heuristic

• Step 1: Initialize Define J as the set of potential distribution centers. Open distribution centers at all eligible candidate sites and assign demand nodes to the distribution center that minimizes the total demand-weighted distance.

• Step 2: Allocate Assign the same fraction of demand to all demand locations given the available budget. Then, reallocate budget using the budget reallocation heuristic provided in Sect. 5.1.

• Step 3: Drop Compute the value $\phi _{j}$ for all opened distribution centers as follows:

  $$\begin{aligned} \phi _{j}= & {} \sum _{k,l} fv_{kl}w_{jkl} \min \{ (d_{rk} - \delta _{k}):r \in J \setminus \{ j\}\} \nonumber \\&\quad + \sum _{k,l} v_{kl}y_{jkl} \min \{ (d_{rk} - \delta _{k}):r \in J \setminus \{ j\}\} \end{aligned}$$

  (29)

  where $\delta _{k} = min\{ d_{jk}: j \in J\}$. Close the distribution center with the smallest value of $\phi _{j}/c^{3}_j$. $J \leftarrow J \backslash \{j\} \text { where } j = \text { argmin } \phi _{j}/c^{3}_j$, reassign dispensing locations to the opened distribution centers that minimize the total demand-weighted distance and repeat Step 2.

• Step 4: Terminate If a reduction in the objective function is found by removing a candidate distribution center or the cost of opening distribution centers is greater than the available budget, go to Step 3. Otherwise, take the previous solution and STOP.

The variable $\phi _{j}$ represents the increase in the total demand-weighted distance, while $c^{3}_j$ represents the savings incurred by dropping distribution center j. Therefore, the ratio $\phi _{j}/c^{3}_j$ represents the total demand-weighted distance (i.e., cost) that is increased for each monetary unit saved (i.e., benefit) caused by closing distribution center j. The distribution center with least favorable cost/benefit ratio is dropped.

5.1 Budget reallocation heuristic

The budget reallocation heuristic performed in Step 2 is presented next:

Step 1::

Initialize Sort in ascending order the dispensing locations using the distance to the opened DC that minimizes the total distribution cost, that is $c_{ijl}^1 \text { and } c_{jkl}^2$. Assign 0 to the demand fraction $y_{jkl}$ corresponding to the dispensing location in the first position of the sequence, calculate the saved budget and reallocate the saved budget uniformly among all the dispensing locations (including the one in the first position of the sequence).

Step 2::

Assign Starting from the second element in the sequence of dispensing locations, assign the minimum fraction $y_{jkl}$ to this element, calculate the saved budget and reallocate the saved budget uniformly among all demand fractions $y_{jkl}$

(a):

If the fraction prepositioned is more than allowed, i.e., $y_{jkl} > 1$, assign a value of 1 to that element, calculate the saved budget and reallocate the saved budget among the $y_{jkl}$ elements that have the minimum value.

(b):

If the equity constraint is violated, i.e., $\max y_{jkl} - \min y_{jkl} \ge \alpha$, assign $\min y_{jkl} + \alpha$ to the elements that have maximum value, calculate the saved budget and reallocate the saved budget among all $y_{jkl}$.

Step 3::

Repeat Repeat Step 2 for all dispensing locations.

In order to illustrate how Step 1 in the budget reallocation heuristic is computed, consider the network shown in Fig. 4a which has n = 2 distribution centers, o = 2 dispensing locations and p = 1 relief item. Distances and the minimum total cost for each DC–DL pair are assumed as follows:

$$\begin{aligned} d_{jk} = \begin{bmatrix} 10&20\\ 30&2.5 \end{bmatrix} , \quad \min _i c^{1}_{ij1} + c^{2}_{jk1} = \begin{bmatrix} 12&24\\ 33&6.5 \end{bmatrix} \end{aligned}$$

The minimum cost for each dispensing location (i.e., column-wise) corresponds to the following j indices: $\big [ \begin{matrix} 1&2\end{matrix} \big ]$. Therefore, the distances used for sorting are $\big [ \begin{matrix} 10&2.5\end{matrix} \big ]$. Once distances are sorted in ascending order, dispensing locations are ordered as follows: $\big [ \begin{matrix} 2&1\end{matrix} \big ]$. This means that the first candidate to reduce its budget will be $k=2$ which has the smallest value (i.e., 2.5) in the sorted distance vector $\big [ \begin{matrix} 2.5&10\end{matrix} \big ]$ and the last candidate to modify its budget is $k=1$ with a distance of 10, taken also from the aforementioned sorted distance vector.

Fig. 4

Sequence of solutions when executing the proposed heuristic using the example data

5.2 Example

In this section, we explain how the heuristic works with an example. As shown in Fig. 4a, we consider a network with 2 potential distribution centers, 2 dispensing locations, 1 outside source and 1 relief item. For the sake of simplification, we assume that $c^1_{ijl} = 0$ and $c^2_{jkl} = d_{jk}$. Assigning $c^1_{ijl} = 0$ allows us to disregard the suppliers located in the first level of the relief chain. Available budget is 300, and the cost of opening any distribution center is 100. Tolerable inequity $\alpha$ is set to 0.25, and outside source inefficiency f is set to 3.

After executing Steps 1 and 2, we obtain an objective value of 4725 and the distribution network shown in Fig. 4c. Variables $\phi _{1}$ and $\phi _{2}$ calculated in Step 3 are 5600 and 1225, respectively. Likewise, since $c^3=100$, ratios $\phi _{1}/c^3$ and $\phi _{2}/c^3$ are 560 and 122.5. Since $\phi _{2}/c^3$ is the minimum ratio among all dispensing locations, distribution center B is dropped and the objective value is updated to 4100. Since we find an improvement compared to the previous objective value of 4725, we take the new solution. At this point, we only have one distribution center opened so we stop.

Figure 4 shows the sequence and results of the steps executed using the inventory prepositioning heuristic proposed in Sect. 5. Figure 4a shows the initial network, and Fig. 4b, c shows the solutions found before and after executing the budget reallocation heuristics in Step 2. Figure 4d shows the final solution of the algorithm which is found in the second iteration. The results of the heuristic is that distribution center A should be opened. The optimal flow of relief items is to preposition at distribution center A, 75% of the relief items needed at dispensing location 1 and 100% required at dispensing location 2. Optimal total demand-weighted distance is 4100.

5.3 Effect of outside source inefficiency

Table 2 Comparison of optimal solutions with different values of outside source inefficiency (f)

By using the same example data found in Sect. 5.2, we can observe how the outside source inefficiency parameter f affects the final solution. Let us assume now that the outside source inefficiency parameter f is changed from 3 and set to 2. For analysis, we divide the budget into two categories depending on its use: Warehousing budget is used for setting up distribution centers, while inventory budget is used for procuring relief items. As shown in Table 2, in the case when $f = 2$, the optimal policy dictates that both distribution centers should be opened and the optimal demand-weighted distance is 3525 as opposed to only one when $f=3$ was used and optimal demand-weighted distance of 4100. Since there is a limited budget, inventory left for procuring relief items is reduced when more budget is used for setting up distribution centers. Therefore, the fraction of demand prepositioned is lower ($45\%$ and $20\%$ for dispensing locations 1 and 2, respectively) when $f=2$ compared to the demand prepositioned when $f=3$ ($75\%$ and $100\%$ for dispensing locations 1 and 2). Two additional aspects to note are that both solutions utilize all the available budget and are at the maximum tolerable inequity.

Based on this example, we can conclude that if outside source inefficiency f is small (i.e., outside source can serve almost as fast as the coordinator), more warehouses are opened and thus disaster response—measured in demand-weighted distance—is improved. On the other hand, if outside source inefficiency f is large (i.e., outside sources take, on average, more time to response to the disaster than the coordinator), less warehouses are opened and more prepositioned supplies are used; in other words, relief supplies prepositioned by the coordinator are preferred over relief supplies provided by outside sources.

6 Computational experiments

In this section, we evaluate the performance of the proposed robust formulation as well as the heuristic by using randomly generated instances, based on the geography of the state of North Carolina, USA. To this aim, we first introduce the methodology for generating the instances used to test our proposed formulations and heuristic. Second, the robust formulation is evaluated comparing the robust solutions with: (1) the deterministic solution and (2) a number of simulated realizations. Third, budget allocation decisions are analyzed for different values of outside source inefficiency and demand variability. Finally, heuristic performance is evaluated and compared to optimal solutions. All experiments were performed on a computer with Intel Core i5 2.4 GHz CPU and 8 GB RAM. The proposed heuristic was implemented in Julia 0.5.2, while optimal nominal and robust solutions were found using Gurobi 7.5.1.

6.1 Methodology for randomly generating instances

We consider a major aid agency or a state government agency, which acts as the coordinator, that wants to design a prepositioning strategy for the state of North Carolina. Suppliers, potential distribution center locations and dispensing locations are randomly chosen from the subset of 5-digit zip codes of the state of North Carolina which have a population greater than 3000. This results in 518 zip codes, from a total of 806 possible zip codes. The database used to obtain population information is found in Kay (2013). Great circle distance with a 1.2 correction factor is used to simulate driving distance between nodes. Nodes are chosen using a demand-weighted distribution. This means that nodes with a larger population have higher probability of being chosen than nodes with a smaller population. As in Rawls and Turnquist (2012), we assume relief items types to be consumables or non-consumables, and thus, two relief item types are considered ($p=2$). Nominal demand quantity is computed as 10% of the population at each dispensing location. For the case of consumable items, we assume that we must preposition sufficient inventory to serve the needs equivalent to five days.

Table 3 Procurement and transportation cost rates for relief items

Fig. 5

Randomly generated instance of a relief network with 5 suppliers, 10 potential distribution centers and 15 dispensing locations

Cost parameters used in the proposed models are calculated as follows: $c^1$, which represents the cost of prepositioning, considers the procurement cost and the pre-disaster transportation cost. $c^2$, which expresses the distribution cost from distribution centers to dispensing locations, is calculated using the post-disaster transportation cost. The cost of opening and setting a distribution center (i.e., $c^3$) is set to $\$150,000$. Procurement costs as well as transportation cost pre- and post-disaster are summarized in Table 3, and procurement costs are uniformly generated between 13 and 17 for consumable relief items and between 23 and 27 for non-consumable relief items. Procurement and transportation cost calculations are based on the case study found in Rawls and Turnquist (2012). In our model, relief items are only prepositioned at the distribution centers, which implies that transportation of prepositioned items to dispensing locations will occur after the disaster has taken place. As observed by Galindo and Batta (2013a) and others, delivery cost after a disaster has occurred become larger due to road and infrastructure damage. For evaluation purposes, we assume an increase of $30\%$ in post-disaster transportation cost compared to pre-disaster.

6.2 Optimization results

By using the methodology described in Sect. 6.1, we randomly generate one instance of size $[m,n,o] = [5,10,15]$, that is 5 suppliers, 10 potential distribution centers and 15 dispensing locations (see Fig. 5). Since there are two relief item types, the maximum number of uncertain demand parameters is 30. Hence, protection level $\Gamma$ can take any integer value in [0, 30]. Available budget b is set to $2,000,000. Outside source inefficiency f is set to 1.5. Storage capacity at each distribution center is calculated as 70% of the total storage space required. Disruptions at links connecting distribution centers to dispensing locations 1, 3 and 4 are assumed to be uncertain, i.e., ${\mathcal {L}}=\{1,3,4\}$. Link capacity reduction is set to 0.1.

Fig. 6

Sensitivity of the proposed robust model compared to the deterministic model under different demand variabilities $\epsilon$ (left) and outside source inefficiencies (right)

First, we compare the robust with the nominal value for two different demand variabilities (i.e., $10\%$ and $20\%$), outside source inefficiencies f and protection levels $\Gamma$. Percentage change in the objective value shown in Fig. 6 is computed as $(Z(\Gamma )^{R} - Z^{N})/Z^{N}$, where $Z(\Gamma )^{R}$ is the robust objective value as a function of protection level $\Gamma$ and $Z^{N}$ is the nominal objective value.

Figure 6a shows the percentage change in the objective value when varying demand variability for different protection levels $\Gamma$. In particular, the percentage change in objective values at protection level $\Gamma = 10$ is approximately 9% and 18% for demand variability $\epsilon = 10\% \text { and } 20\%$, respectively. At protection level $\Gamma = 30$, which yields the most conservative solution, the percentage change in objective values is approximately 11% and 23%. This figure also reveals a higher rate in the percentage of change for low protection levels compared to higher protection levels. Figure 6b shows the percentage change in the objective value when varying outside source inefficiency for different protection levels $\Gamma$. As we can observe in Fig. 6b, a similar trend is followed when outside source inefficiency is increased.

In our model, the probability of constraint violation is the fraction of demand realizations that a given solution is not able to fully serve due to insufficient budget or inventory. In other words, a lower probability of constraint violation is associated with a higher level of protection $\Gamma$. Figure 7 shows the probability of constraint violation for different levels of protection. The equation used to derive the probabilities shown in Fig. 7 can be found in Bertsimas and Sim (2004). As suggested by Bertsimas and Sim (2004), the probability of constraint violation can be used as a guidance to select the protection level $\Gamma$. For instance, if the modeler wants to find a solution with a probability of constraint violation less than 5%, a protection level $\ge 10$ should be selected. On the other hand, if the maximum tolerable probability of constraint violation is desired to be $1\%$, a protection level of at least 14 should be chosen.

Table 4 summarizes the optimal objective value when varying the set of links with uncertain capacities ${\mathcal {L}}$ and the link capacity reduction ${\hat{u}}$. As expected, higher magnitudes of link disruption and number of links with uncertain link capacity significantly increase the objective value, i.e., total demand-weighted distance. Experiments conducted with different values of demand variability $\epsilon$ and protection level $\Gamma$ show a similar trend.

Fig. 7

Probability of constraint violation under different protection levels $\Gamma$

Table 4 Percentage change in objective value for different link capacity maximum reductions ${\hat{u}}_{k} \quad \forall k \in {\mathcal {L}}$ and sets of links with uncertain capacity ${\mathcal {L}}$

6.3 Simulation results

Fig. 8

Simulation results for maximum, minimum and expected total weighted distance for different protection levels $\Gamma$. Total demand-weighted distance, i.e., the y-axis, is given in millions. Outside source inefficiency f is set to 1.5, unmet demand is penalized by a factor of 10f, demand variability $\epsilon$ is set to 0.5, and no link capacity is considered uncertain

We have argued that the level of protection $\Gamma$, which is a parameter chosen by the modeler, affects the quality of the robust solution. In order to properly choose the level of protection, Dunning (2016) suggests to evaluate the performance of the robust solution by simulating several realizations of the uncertain parameters. To this aim, we simulate 1000 demand realizations for each robust solution found by varying the protection level.

In order to fairly evaluate the quality of the robust solution, we must make some assumptions. First, we assume that the amount of relief items prepositioned and the distribution centers opened cannot be changed but the actual distribution of relief items to dispensing locations can be changed depending on the demand realization. The logic behind this assumption is that prepositioning and setting up a distribution center takes time and must occur before the demand is realized while the distribution of prepositioned supplies to the dispensing locations is done after demand is known. Second, we assume that demand realizations are independent and uniformly distributed in the range $[v_{kl} - {\hat{v}}_{kl}, v_{kl} + {\hat{v}}_{kl}]$. Perturbation ${\hat{v}}_{kl}$ is computed as follows: ${\hat{v}}_{kl} = \epsilon {v}_{kl}$ where $\epsilon$ is referred to as the demand variability. Lastly, unmet demand is penalized in the objective function with a factor of 10 times the outside source inefficiency (i.e., 10f).

Table 5 Simulation results given by the robust solution for different protection levels $\Gamma$

Simulation results are summarized in Fig. 8 and Table 5. Figure 8 shows the expected objective value, the maximum and the minimum values using different robust solutions. Two zones with different behavior can be identified in the figure. When the protection level $\Gamma \le 10$, there is a consistent decrease in the expected and maximum objective values resulting in less variability. For $\Gamma \ge 10$, the solution objective becomes insensitive to the protection level. This finding indicates that the protection level does not need to be adjusted to more than 10 to achieve the best expected results. Table 5 shows a summary of the simulation results depicted in Fig. 8. For instance, by setting the protection level $\Gamma = 10$, the expected objective value decreases by $29\%$ and the change in variation, measured as the standard deviation, decreases by $47\%$. Similar numbers can be found for protection levels between 10 and 30.

6.4 Budget allocation

In this section, we derive some insight on how the budget is allocated for different protection levels $\Gamma$, demand variability $\epsilon$ and outside sources inefficiencies f. As we did in Sect. 5, for analysis purposes we divide budget into two categories depending on its use: Warehousing budget is used for setting up distribution centers, while inventory budget is used for procuring relief items.

We consider a problem with 10 suppliers, 20 potential distribution center locations and 30 dispensing locations. Capacities are assumed uncertain in those links connecting dispensing locations 1, 3 and 4 with an uncertain link capacity reduction of 10%. Figure 9 shows the effect the outside source inefficiency factor f has in budget allocation decisions. We consider two demand variabilities $\epsilon$ as well as two protection levels $\Gamma$. Figure 9a–d shows a similar behavior for each of these scenarios. For outside source inefficiencies between 1 and 2, i.e., $1 \ge f \le 2$, there is a steep increase in the budget spent in prepositioned relief items resulting in less distribution centers opened. For $2 \ge f \le 5$, we observe that budget allocation is insensitive to the value of f with the exception of a phase transition at $f \approx 3.5$ where budget assigned to procure inventory reach a maximum. This phenomenon can be explained by looking at the effect of the factor f on the objective value. The factor f is multiplying the demand-weighted distance of the fraction of demand served by the outside sources. Assuming $f > 1$, the objective value increases, i.e., deteriorates since it is a minimization problem, when the factor f increases. Therefore, when the factor f increases, the model tries to reduce its negative effects in the objective value by prepositioning more relief supplies, i.e., reducing the fraction of demand served by the outside sources, and decreasing the number of opened distribution centers given the limited budget.

Fig. 9

Budget of $4 million allocated to opening distribution centers and inventory cost when varying outsource inefficiency f. Two different demand variabilities (i.e., $\epsilon = 0.1$ and $\epsilon = 0.2$) and protection levels (i.e., $\Gamma = 3$ and $\Gamma = 10$) are evaluated. A problem with 10 suppliers, 20 potential distribution centers and 30 dispensing location is considered. Capacities are assumed uncertain in those links connecting dispensing locations 1, 3 and 4 with an uncertain link capacity reduction of 10%

6.5 Effects of storage capacity

In this section, we conduct a comparative analysis considering distribution centers with five different storage capacities and two values of penalty parameter f. The levels of storage capacity are reported in units as well as in percentage (%) of total demand. We vary this number from very low ($< 3\%$) to very high ($>20\%$). We compare resulting objective values, the number of opened distribution centers, the number of opened distribution centers used at full capacity and the percentage of nominal demand prepositioned.

Table 6 shows that better objective values are found using a sparse and decentralized network, i.e., many small distribution centers, rather than a centralized network with few large distribution centers. We believe this observation is due to the definition of the objective function. Because the objective function minimizes the demand-weighted distance between distribution centers and demand locations, its value decreases or stays the same as the number of opened distribution centers is increased. When comparing the effect of the parameter f, we can observe that a high value of f, i.e., $f=4.5$, increases the amount of prepositioned relief items and reduces the number of opened distribution centers compared to the results obtained with a low f, i.e., $f=1.5$. The managerial insight of these results is that the use of prepositioned relief items, which are ready to ship immediately after the disaster occurs, increases when outside sources’ help is highly penalized.

Table 6 Comparative analysis considering distribution centers of different sizes and setup cost

6.6 Heuristic performance

In this section, we show the results of two experiments. First, we evaluate the performance of our heuristic. Second, we characterize the cases where our heuristic works well for capacitated problems.

In the first experiment, we evaluate how the heuristic performs using two measures: optimality gap (i.e., error) and computational time. Error is calculated using $[(Z^{H} - Z^{*})/Z^{*}] \times 100\%$ where $Z^{H}$ is the heuristic objective value and $Z^{*}$ is the optimal objective value. Computational time is calculated in seconds.

Results are reported in Table 7. Problem sizes are defined by the number of suppliers |J|, the number of potential distribution centers |K|, the number of dispensing locations |L| and two relief items. Error reported in Table 7 is the average of the error of ten replications. Based on these results, heuristic solutions show an average error less than 1.7% for all instances and the maximum error found is 2.9%. Regarding computational time, all heuristic instances were solved in less than ten seconds, which is good enough for the conditions in which the heuristic is intended to be used. Furthermore, when the proposed heuristic is used to provide an initial feasible solution, the average computational time to find an optimal solution is reduced by 40%.

Table 7 Computational time comparison between the heuristic and the deterministic uncapacitated version of the proposed model

In the second experiment, we evaluate optimal and heuristic solutions considering distribution centers with five different storage capacities and two values of penalty parameter f. We compare objective values, the number of opened distribution centers and the number of distribution centers used at full capacity. We consider a problem with 10 suppliers, 20 potential distribution centers, 30 dispensing locations and a budget of $4 million. We assume demand is deterministic and no link disruptions.

Table 8 shows that heuristic solution violates capacity restrictions only for the smallest distribution centers considered in the experiment, i.e., setup cost of $70000 and storage capacity of 13000 units, which represents 2.5% of total nominal demand. For the remaining cases, the storage capacities are not exceeded; hence, the solution can be fairly compared to the optimal solution which considers capacity constraints. In these cases, the heuristic provides solutions within 0.4% compared of the optimal policy. This occurs with both values of the parameter f studied.

Table 8 Comparison of optimal solutions considering capacity constraints with heuristic solutions

7 Conclusions and future research

In this paper, we address the problem of prepositioning supplies in preparation for a disaster under uncertainty in demand and link disruption considering a multi-agency disaster response. We examine an inventory prepositioning problem from the perspective of the main aid agency considering sharing distribution centers with other agencies. We model a multi-commodity three-echelon relief item chain that consists of suppliers, distribution centers and dispensing locations. The objective of our model is to minimize total demand-weighted distance from distribution centers to dispensing locations while considering storage capacity, budget and equity constraints. Demand uncertainty is modeled using the budget uncertainty set approach proposed by Bertsimas and Sim (2004). Uncertainty in link disruption is modeled using the interval uncertainty set proposed by Soyster (1973).

Additionally, we develop and test a heuristic approach to solve the uncapacitated deterministic version of our proposed model. The E-IP algorithm begins by choosing which distribution centers to open and a fraction of prepositioned demand for all dispensing locations and relief items considering that all distribution centers are available. This is considered as the initial solution. Then, by using a cost-to-benefit ratio as a criterion, the heuristic iteratively closes distribution centers until no further improvement of the objective function is achieved. Experiments show that the heuristic approach achieved solutions within 3% compared to the optimal policy. The heuristic approach proposed in this paper would give practitioners the advantage of solving the deterministic problem without the need for a mathematical model or optimization software. In further studies, we intend to test if computational times when optimally solving the proposed model can be reduced by using the heuristic solution, which is a relaxed solution of the proposed model, as a lower bound.

Robust solutions are analyzed in a series of experiments showing the percentage change in the objective function compared to the deterministic model varying the protection level and the demand variability. We discuss the probability of constraint violation for different protection levels and provide guidelines to choose model parameters. Simulation results show that robust solutions could reduce the expected objective value and standard deviation by 30% and 50%, respectively, compared to the deterministic solutions. Additionally, a sensitivity analysis is performed on the outside source inefficiency factor. We show that outside source inefficiency affects budget allocation decisions; in particular, inventory budget increases and warehousing budget decreases as the outside source becomes more inefficient. Furthermore, as demand variability increases, more is spent on inventory, for a given level of outside source inefficiency.

In this paper, we provide a holistic view of the inventory prepositioning problem. Disaster responses are usually a joint effort between several aid agencies. Previous models seek to optimize the prepositioning strategy for one aid agency. In some cases, the single-agency approach to the prepositioning problem could lead to a suboptimal disaster response since, as we demonstrated in this paper, budget allocation decisions are affected by the characteristics of the other agencies involved in the disaster response. Several directions of future work have been identified. (1) Our heuristic could be extended to find robust solutions considering capacitated distribution center locations. (2) In some cases, uncertain parameters are correlated. For instance, demand for relief supplies may depend on where the disaster strikes. Therefore, a more realistic model can be constructed by considering correlated data. (3) Several sources of uncertainty, such as supply availability and cost parameters, can be incorporated into the model following the same approach used to model demand uncertainty.