A Stochastic Optimization Model to Reduce Expected Post-Disaster Response Time Through Pre-Disaster Investment Decisions

Abstract

This paper seeks to enhance network survivability under a disaster and reduce the expected post-disaster response time for transportation networks through pre-disaster investment decisions. The planning focuses on determining the links of the network to strengthen through investment under two types of uncertainties: the disaster characteristics, and the surviving network under each disaster. A bi-level stochastic optimization model is proposed for this problem, in which link investment decisions are made at the upper level to enhance the network survivability subject to a budget constraint such that the expected post-disaster response time is minimized at the lower level. A two-stage heuristic algorithm is proposed to obtain effective solutions efficiently. The numerical experiments indicate that the proposed heuristic algorithm converges to a fixed point representing a feasible solution, within an acceptable tolerance level, of the bi-level stochastic optimization model which is an effective solution under disasters of moderate severity. Parametric and sensitivity analyses reinforce the need for a holistic approach that integrates multiple relevant considerations to determine the link investment decisions.

1 Introduction

Disasters, either natural or man-made, can cripple the functionality of the lifeline infrastructure systems such as transportation networks, power systems, water networks, and communication networks, causing severe human and economic loss, and disrupting the day-to-day activities of human beings (Baum et al. 1983). Previous research (Hwang et al. 2000; Abdel-Rahim et al. 2007; Kiremidjian et al. 2002; Peeta et al. 2010) has illustrated that the survivability of infrastructure networks under disasters can be enhanced by strengthening their components structurally. However, this process usually entails significant monetary costs. Typically, the more severe random disasters are less likely to occur, and the improvement of all vulnerable links and infrastructure components to the degree of withstanding disasters of extreme severity would entail unacceptable expenditures. This implies the need to allocate the limited resources to holistically achieve some disaster-related operational goals, leading to the pre-disaster investment planning problem addressed in this paper.

Two aspects are usually considered in the context of the pre-disaster investment planning problem, the pre-disaster planning and the post-disaster response (Towfighi 1991). The pre-disaster planning stage involves strategic decision-making for risk assessment and management, infrastructure improvement to reduce vulnerability to disasters, enhancement of system resilience, and developing emergency response plans. Thereby, long-term cost-effectiveness and investment benefit maximization are key goals which shape the strategic decisions at this stage. The post-disaster stage involves tactical and operational decision-making (Hsu and Peeta 2013; Yao et al. 2009) in the short- and medium-terms in order to provide critical recovery and reconstruction services (Matisziw et al. 2010; Sumalee and Kurauchi 2006) to ensure human and property safety, and to provide communication and transportation channels to the affected population. Hence, minimizing response times to the affected areas and the effective deployment of required resources represent major goals in the post-disaster stage (Holguín-Veras et al. 2012). While the two stages focus on different aspects of disaster management, they are interdependent as the expected post-disaster system performance is a key factor for strategic decision-making at the pre-disaster planning stage. Correspondingly, the investment decisions in the pre-disaster stage can be leveraged for effective response in the post-disaster execution stage. Investment decisions that do not incorporate this interdependence may not lead to the expected levels of post-disaster response performance. Hence, this study proposes a pre-disaster investment planning framework in which these two stages are integrated seamlessly.

From a transportation network functionality perspective, an important issue for pre-disaster investment planning is the need to adequately capture the randomness associated with link failures arising from the disaster impact. However, the disaster impact itself is dependent on the randomness in disaster characteristics. Hence, two sources of stochasticity need to be considered; the uncertainty related to disasters that reflects the likelihood of different disasters, and the likelihood of link failures under a certain disaster. The link failure is linked to the investment decision in the sense that monetary investments in the link structural or functional components can be used to enhance link survivability. In this context, this study models the individual link investment decision as a continuous variable between zero and one. That is, a link can be partly invested in, and correspondingly, it can proportionally impact the link failure probability distribution. While the consideration of the interactions among link investment decisions, disaster randomness, and link failure distributions can ensure more realism in addressing the pre-disaster investment planning problem, they also significantly increase the problem complexity of the proposed study.

While disasters can lead to link failures and investment can enhance their survivability, the key goal of the pre-disaster investment planning problem is to identify the subset of network links to invest in under the budget limitation. That is, strengthening links to increase their survivability under disasters entails some upgradation costs, implying the need to identify which links to invest in. In this context, we holistically consider three factors including the importance of a link to network connectivity, the role of a link in the context of network traffic flow, and the marginal survivability increase for a link under a certain level of investment, to identify the links to potentially invest in. The study develops a bi-level stochastic optimization model to identify the pre-disaster link investment decisions by integrating the three factors associated with link characteristics and the post-disaster network performance related to response times (the time taken by a disaster response team to reach an affected area).

The remainder of the paper is organized as follows. The next section reviews the literature. This is followed by some mathematical preliminaries that describe the problem. Then, a bi-level stochastic optimization model is proposed for the pre-disaster investment planning problem. Next, the solution algorithm is discussed. Numerical experiments are then discussed, followed by some concluding comments.

2 Literature Review

The pre-disaster investment planning problem seeks to allocate a limited pre-disaster investment budget to strengthen links so that the network performance under a disaster is enhanced. In the literature, a possible related area is survivable network design which has been extensively studied (Grotschel et al. 1995; Soni et al. 1999; Kerivin and Mahjoub 2005) in computer networks. However, unlike computer networks, transportation networks do not usually have hierarchical structures, and therefore the associated methodologies are not particularly relevant.

Survivable network design has also been studied in the operations research domain to identify key links to connect origin–destination (O-D) pairs for specific application contexts. Ball et al. (1989) and Malik et al. (1989) propose algorithms to determine the k-most vital arcs whose removal from a network results in the greatest increase in the shortest distance between two specified nodes. Chen et al. (2007) present network-based accessibility measures for assessing vulnerability of degradable transportation networks. They can be used to identifying critical components in realistic road networks and to design reliable and robust networks. The study factors the consequence of link failures in terms of travel time or generalized cost increase, as well as the behavioral responses of users due to link failure. Matisziw and Murray (2009) develop a constraint structure which identifies infrastructure vital to system flow without enumerating all origin–destination paths. These studies mostly consider deterministic link failures and static surviving network topologies and do not factor stochastic link failures and the corresponding uncertainty in the surviving network topologies under disasters. Murray-Tuite and Mahmassani (2004) develop a bi-level formulation to identify vulnerable transportation links in the context of network disruption. They propose a vulnerability index that factors the availability of alternate paths, excess capacity, and travel time to determine the critical links, but model link failures deterministically. Latora and Marchiori (2005) and Nagurney and Qiang (2007) also propose methods to identify the critical components in a congested network and a general infrastructure network, respectively, considering deterministic component removal. Abdel-Rahim et al. (2007) use a macroscopic simulation model to investigate the effects of electric power outages on the operation of a transportation network under intelligent transportation systems. Based on that, a multilayer graph-based method is proposed to assess the importance of different components in critical infrastructure networks. The simulation model factors various operational aspects, but does not explicitly account for the randomness of link failures under disasters. Ukkusuri and Yushimito (2009) propose a heuristic procedure to assess the criticality of highway transportation infrastructure in a transportation network. Travel time capturing the congestion effects is used to evaluate the impact of removing individual links or nodes. In summary, the aforementioned literature does not factor the stochasticity associated with link failures arising from the randomness in disaster characteristics, which is a key real-world aspect and represents a primary focus of our study. Further, it does not account for the interactions between individual link failures and investment planning. This capability is especially important to aid investment decision-making to strengthen infrastructure to enhance survivability and performance under disasters, which is the key application objective of this paper.

Several studies (Moghtaderi-Zadeh and Der Kiureghian 1983; Small 2000; Sohn 2006; Bana e Costa et al. 2008; Liu et al. 2009; Fan and Liu (2010); Peeta et al. 2010; Porter and Ramer 2012) have sought to identify a subset of vital/critical links in transportation networks by considering upgrade costs and post-disaster network performance. The proposed study differs from them in two key aspects. First, most of these studies identify critical links using only local factors specific to a link rather than the holistic consideration of the importance of a link to the overall system. For example, Moghtaderi-Zadeh and Der Kiureghian (1983) determine the failure of an individual link based on a distance threshold to an earthquake, and then identify critical links to maximize system reliability. Similarly, Werner et al. (1997) and Small (2000) prioritize the links in a transportation network based on link-specific factors such as the physical condition and the cost to upgrade the link to withstand disasters of specific intensities. Second, most of these studies are addressed in the context of a specific disaster scenario rather than for multiple disasters, precluding the ability to fully capture the dependence of link failures on the variability of the disaster characteristics. For example, Sohn (2006) evaluates the significance of an individual link for a transportation network in the context of flooding. Bana e Costa et al. (2008) and Liu et al. (2009) develop quantitative models to prioritize bridges and tunnels for seismic retrofitting. Fan and Liu (2010) propose a two-stage stochastic program to choose the best set of network components to protect in a pre-disaster context. While the study is not disaster-specific, the dependence of link failures on the variability of the disaster characteristics is not considered.

More recently, Peeta et al. (2010) propose a related study that formulates a two-stage stochastic model for the pre-disaster investment planning problem to reduce the post-disaster response time under a disaster. Our work extends Peeta et al. (2010) in three key aspects; they add analytical complexity while more holistically factoring real-world considerations from the perspective of decision-makers. First, this study explicitly models the randomness due to the disaster characteristics. By contrast, Peeta et al. (2010) consider only a single disaster scenario. A key consequence of the explicit consideration of the stochasticity of disaster characteristics in addition to that of link failures is that the problem complexity is significantly enhanced beyond that of Peeta et al. (2010). Second, Peeta et al. (2010) assume that the link investment decisions are 0-1 integers rather than the [0,1] continuous variables as proposed in this study. Modeling the investment decisions as continuous variables provides decision-makers the flexibility to partly invest in a link rather than making a limiting discrete decision on whether to invest in it or not. Hence, it provides decision-makers more solution options in practice. Third, this study holistically evaluates the importance of a link in terms of three factors: connectivity, link usage in terms of flow, and survivability improvement relative to the upgradation cost. Peeta et al. (2010) consider only connectivity. The three factors further serve to bridge the optimization models at the two levels in the proposed bi-level optimization model, thereby enabling the investment decision and surviving network estimation to be considered in an integrated manner rather than in separate stages as in Peeta et al. (2010). In addition, due to the different in the modeling approach used, this study proposes a two-stage heuristic algorithm to obtain the feasible investment solution based on our bi-level optimization model while Peeta et al. (2010) use a first order approximation based solution procedure to solve their two-stage stochastic model.

In summary, the proposed study is different from the aforementioned literature primarily in the following aspects: (i) two levels of stochasticity (link failures and disaster characteristics) are explicitly considered in the modeling process to link pre-disaster planning to post-disaster response, (ii) the investment decisions are modeled as continuous variables between zero and one, and (iii) multiple factors (such as connectivity, traffic flow, and marginal survivability improvement) are considered to characterize the importance of a link holistically at the network level. Thereby, this study provides more flexibility from the perspective of decision-makers, addresses some key gaps related to realism and adequacy in the current literature in this problem context, and entails greater problem complexity.

3 Mathematical Model

This section discusses the proposed mathematical approach to address the pre-disaster investment problem. The mathematical formation is presented, followed by a discussion of the three factors that characterize the importance/significance of a link in the investment decision context: the importance of a link to network connectivity, the role of a link in the context of network traffic flow, and the marginal survivability improvement for a link under a certain level of investment. Then, a bi-level stochastic optimization model is developed to address the problem.

3.1 Mathematical Formulation

This study considers a transportation network potentially affected by a natural or man-made disaster in a geographical region containing some population. The network is represented by a directed network G(N,E) with node set N and link set E. Each node is assumed to cover some population in its vicinity in terms of access. A directed link in the network between nodes i and j is denoted by [i, j]. The free-flow travel time on link [i, j] is assumed known and denoted by t _ij . The disaster response plan typically seeks to reduce the post-disaster response time (on the transportation network) for the response resources located in large urban areas to reach large population centers. The study considers the relative importance of O-D pairs based on the populations of the associated nodes and the corresponding need for response resources (medicine, food, clothing, machinery, etc.). It assumes that the decision-maker can determine this by assigning weights to O-D pairs by factoring population size, level of service related to response, and the available resources. Thereby, each O-D pair k is weighted using a positively-valued weight α _k to reflect its level of importance. This identifies a set of O-D pairs whose response time is a key focus in the planning phase. To verify post-disaster connectivity, one unit of flow must be transported over the (surviving) network from origin O(k) to destination D(k). If the post-disaster status of the network is such that one of the O-D pairs cannot be connected, then a large penalty cost is incurred to reflect the critical deterioration in the response performance for an important component of the disaster response plan. In addition, it is noted that the focus of the planning problem is to ensure that emergency response personnel and equipment can reach from the various origins to their destinations in the least possible travel time immediately after the disaster. Hence, the planning problem context assumes that the links are not congested (especially under disasters such as earthquakes), and that the response operations ensure that these resources can travel at the link free-flow travel times on the corresponding paths.

Each link of the network is subject to multiple disaster scenarios, represented by the random variable ω. The possible set is denoted by Ω = {ω _d } ^|Ω| _d = 1 . Each disaster scenario ω _d occurs with a probability denoted by Γ (ω _d ). Under a certain disaster, an individual link can fail independently and correspondingly its capacity will reduce from one to zero; otherwise the link is assumed to survive with full capacity. Typical examples are bridges under earthquakes, which usually either survive with full functionality or fail. The link survivability, reflected by the link survival probability under a certain disaster, can be improved by upgrading it during the pre-disaster stage. The investment decision for each link is defined as a continuous decision variable between zero and one. It represents the link investment rate rather than a specific monetary value. Namely, y _ij  = 1 indicates that the link is fully upgraded; y _ij  ∈ (0,1) means the link is partially upgraded, and y _ij  = 0 implies that the link is not upgraded. The investment strategy for the network is represented by a vector  y = {y _ij }^|E|, y _ij  ∈ [0,1]. Accordingly, the disaster dependent link failure probability θ_ij is calculated by a linear interpolation method. That is, θ_ij(ω_d) = p_ij(ω_d)–y_ij(p_ij(ω_d) − q_ij(ω_d)), where q_ij(ω_d) is the link failure probability under disaster ω_d if it is fully upgraded, and p_ij(ω_d) is the link failure probability under disaster ω_d if it is not upgraded. Link survivability is the complement of the link failure probability. Hence, the probability of link failure depends on the disaster randomness and the investment strategy. It should be noted here that the link failure probability boundaries p_ij(ω_d) and q_ij(ω_d) can be calibrated using historical data, or through risk and material mechanistic analyses, as illustrated by structural engineers (Small 2000; Loh et al. 2003; Ramirez et al. 2005). Thereby, while disasters can occur randomly, the effect of a specific disaster type on a specific infrastructure type can be estimated through risk analysis since the features of disasters and infrastructure can be characterized. Thereby, without loss of generality, other calibrated interpolation methods can be used here instead of the linear interpolation method based on the data availability.

The full upgradation cost for link [i,j] is denoted by c_ij. Then, B = ∑ _[i,j]c_ij is the budget needed to fully upgrade the entire network, and b = rB is the limited budget indicating that only the fraction r of the full network upgradation budget, r ∈ [0,1], is available.

The post-disaster state of a link [i,j] is denoted by a random variable  ξ _ij , which takes the value 1 if link [i,j] survives the disaster, and 0, otherwise. A vector of the random variables ξ _ij over all links in E, denoted by ξ = {ξ _ij }_{[i,j] ∈ E} , indicates a “surviving network”. The set of all surviving networks is denoted by Ξ = {ξ ^s} ^|Ξ| _s = 1 . The conditional probability P(ξ ^s|y, ω _d ) is used to denote the likelihood that the post-disaster network scenario ξ ^s is realized given the investment decision strategy y and the disaster scenario ω _d . It can be computed as:

$$ \begin{array}{l}P\left(\left.{\xi}^s\right|y,{\omega}_d\right)={\displaystyle \prod_{\forall \left[i,j\right]\in E}}\left\{{\xi}_{ij}^s\right.\left[1-{p}_{ij}\left({\omega}_d\right)+{y}_{ij}\left({p}_{ij}\left({\omega}_d\right)-{q}_{ij}\left({\omega}_d\right)\right)\right]\hfill \\ {}\left.+\left(1-{\xi}_{ij}^s\right)\left[{p}_{ij}\left({\omega}_d\right)-{y}_{ij}\left({p}_{ij}\left({\omega}_d\right)-{q}_{ij}\left({\omega}_d\right)\right)\right]\right\}\hfill \end{array} $$

(1)

Associated with the surviving network, this study defines the binary decision variable x ^k _ij (ξ ^s|(y,ω _d )), which is equal to 1 if there is one unit of flow of the commodity k (that is, the O-D pair k) on link [i,j] given the realization of  ξ ^s resulting from the investment strategy y and the disaster  ω _d , and 0, otherwise. The flow in the whole network is denoted by x. The network performance is captured by the expected travel time for the initial emergency response after a disaster. Mathematically, the expected disaster response time over the surviving networks under all possible disasters is given below:

$$ \mathrm{F}\left(\mathrm{x}\right)={\displaystyle {\sum}_{\mathrm{d}\in \Omega}\Gamma \left({\upomega}_{\mathrm{d}}\right)}{\displaystyle {\sum}_{\mathrm{s}\in \Xi}\mathrm{f}\left(\mathrm{x}\left(\left.{\upxi}^{\mathrm{s}}\right|\left(\mathrm{y},{\upomega}_{\mathrm{d}}\right)\right)\right)}\mathrm{P}\left(\left.{\upxi}^{\mathrm{s}}\right|\mathrm{y},{\upomega}_{\mathrm{d}}\right) $$

(2)

where f(x(ξ ^s|(y,ω _d ))) is the sum, over all O-D pairs, of the shortest response time for each O-D pair in the surviving network (ξ ^s|y, ω _d ). Mathematically, it can be computed by Eq. (3), where a large penalty cost M is used to denote the response time for an O-D pair if it is not connected due to link failure in the surviving network (ξ ^s|y, ω _d ). Considering that the number of surviving networks will increase exponentially with the size of the network, this study approximates the value of F(x) using Monte Carlo simulation in the proposed solution algorithm.

$$ f\left(x\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)\right)=\left\{\begin{array}{c}\hfill { \min}_x{\displaystyle {\sum}_{k\in K}{\alpha}_k}\left[{\displaystyle {\sum}_{\left[i,j\right]\in E}{t}_{ij}{x}_{ij}^k\left({\xi}^s\left|\left(y,{\omega}_d\right)\right.\right)}\right],\kern1em if\kern1em x\left({\xi}^s\left|\left(y,{\omega}_d\right)\right.\right)\ne \varnothing \hfill \\ {}\hfill M, otherwise\hfill \end{array}\right.. $$

(3)

As stated earlier, in the planning problem context, the first responders move towards the disaster-affected areas with prioritized right of way, consistent with the assumption that the links are not congested, and that travel occurs based on the link free-flow travel times on the corresponding paths. From a planning perspective for the first responders, a potential highly congested link is treated as a link failure which may interrupt the connection between the corresponding O-D pairs.

Based on the above assumptions and definitions, a bi-level stochastic optimization model is proposed in the next section for the pre-disaster investment planning problem.

3.2 Link Significance

The prioritization of links for receiving investment to strengthen them for post-disaster survivability is based on holistically considering three factors that are important to response time reduction.

3.2.1 Link Significance to Network Connectivity

This section develops the mathematical formulation to evaluate the significance of individual links to network connectivity. The links whose removal/failure has a higher impact on the network connectivity are weighted more. Equation (4) incorporates the contribution of a link to the network connectivity in two aspects. The first component in Eq. (4) measures the significance of a link to the network connectivity in terms of network flow reduction if it fails under a disaster. As shown in Eq. (5), it is represented by the expected traffic flow reduction of the network maximum flow over all disaster scenarios, across all O-D pairs due to the failure of link [i,j]. Note that the traffic flow reduction (Δf ^max _ij ) is weighted by the link survivability under each disaster and the relative importance of each O-D pair. The second component of Eq. (4) addresses the significance of a link to the network connectivity when this link fails along with other links in a disaster, which implies the dependence between links, and is a more typical situation in disasters. The study recognizes that it is difficult to identify the importance of each failed link set to the network connectivity, given the intractable number of such combinations under various surviving networks. To circumvent this difficulty, the approach emphasizes the set of failed links which disconnect the O-D pair in a surviving network, but belong to the link set which composes the shortest path to connect this O-D pair in the original network topology  G (that is, when no link fails). This is illustrated in Eq. (6). This implies the perspective that these links are the most significant set of links for the O-D pair as their survival can result in the “best” shortest response time for that O-D pair. Correspondingly, if the surviving network disconnects an O-D pair, we uniformly increase the weights of the failed links belonging to this set by one unit as part of our solution algorithm. The increased weights of the links improve their likelihood to be invested in the pre-disaster plan so that their survivability is improved. The denominators in Eqs. (5) and (6) are to enable normalization for ensuring that W ^c _ij is dimensionless.

It is important to note here that the first component in Eq. (4) is a deterministic value, mainly factoring the link significance to the network connectivity in terms of link capacity. However, the second component is a dynamic value depending on the topologies of the original network and the surviving networks under disasters. As defined by Eqs. (6) and (7), the second component can be zero when the surviving network connects all O-D pairs. As there is no a priori data to indicate whether one of these two components is more important to sustain network connectivity under disasters, we weigh them equally in the mathematical model and provide the sensitivity analyses for the weights of these two factors in Section 6.2.5.

$$ {W}_{ij}^c={W}_{ij}^{c1}+{W}_{ij}^{c2} $$

(4)

$$ {W}_{ij}^{c1}={E}_{\omega}\left[{\displaystyle {\sum}_{k\in K}{\alpha}_k}\left(1-{y}_{ij}{q}_{ij}\left(\omega \right)\right)\varDelta {f}_{ij}^{\max}\right]/{\displaystyle {\sum}_{\left[i,j\right]\in E}{W}_{ij}^{c1}} $$

(5)

$$ {W}_{ij}^{c2}={E}_{\omega}\left[{\displaystyle {\sum}_{k\in K}{\alpha}_k}{\displaystyle {\sum}_{s\in \varXi }{w}_{sij}^k}\right]/{\displaystyle {\sum}_{\left[i,j\right]\in E}{W}_{ij}^{c2}} $$

(6)

$$ {\boldsymbol{w}}_{\boldsymbol{s}\boldsymbol{ij}}^{\boldsymbol{k}}=\left\{\begin{array}{c}\hfill \mathbf{1},\forall \left[\boldsymbol{i},\boldsymbol{j}\right]\mathrm{in}\;\mathrm{the}\;\mathrm{shortest}\;\mathrm{path}\;\mathrm{of}\;\mathrm{commodity}\;\boldsymbol{k}\;\mathrm{in}\;\boldsymbol{G},{\boldsymbol{\xi}}_{\boldsymbol{ij}}^{\boldsymbol{s}}=\mathbf{0},\mathbf{and}\;{\boldsymbol{\xi}}^{\boldsymbol{s}}\mathrm{disconnects}\;\mathrm{O}\hbox{-} \mathrm{D}\left(\boldsymbol{k}\right)\hfill \\ {}\hfill \mathbf{0},\mathrm{otherwise}.\hfill \end{array}\right. $$

(7)

3.2.2 Link Significance to Network Traffic Flow

Next, the link significance to the network traffic flow is explored. As stated earlier, as the response planning context does not factor traffic congestion, we develop a proxy for W ^f, as illustrated in Eq. (8):

$$ {W}_{ij}^f={E}_{\omega}\left[{\displaystyle {\sum}_s\left[{\displaystyle {\sum}_k\left.{\alpha}_k{x}_{ij}\left({\xi}^s\right)\right|\omega, y}\right]}\right]/{\displaystyle {\sum}_{\left[ ij\right]\in E}{W}_{ij}^f} $$

(8)

where [∑ _k α _k x _ij (ξ)|ω, y] represents the O-D weighted frequency that the link [i,j] is part of the shortest path for various O-D pairs in the surviving network ξ ^s. The proxy, W ^f _ij , reflects the expected number of times that link [i,j] is used in the shortest path for the various O-D pairs under all possible network realizations and disasters. The denominator in Eq. (8) is to enable normalization for ensuring that W ^f _ij is dimensionless.

There are two special cases in which we do not count the link significance represented by Eq. (8) to network traffic flow due to no flow on the surviving links: (i) when all links fail in a disaster, and (ii) when the surviving network cannot connect an O-D pair. The significance of the failed links in these two cases is evaluated from the connectivity perspective discussed heretofore.

3.2.3 Marginal Link Survivability Improvement

Finally, the significance of a link based on the marginal survival probability improvement through investment is considered; it is reflected through W ^p _ij . It implies that links whose upgradation cost is low relative to the survivability improvement under disasters can represent attractive candidates from an investment strategy perspective given the limited budget. As stated earlier, the holistic approach used to identify the links to invest in considers this aspect as a factor along with network connectivity significance and traffic flow usage. For a given investment decision  y, the normalized marginal link survivability improvement W ^p _ij is:

$$ {W}_{ij}^p={E}_{\omega}\left[{y}_{ij}\left({p}_{ij}\left(\omega \right)-{q}_{ij}\left(\omega \right)\right)\right]/{\displaystyle {\sum}_{\left[ ij\right]\in E}{W}_{ij}^P} $$

(9)

3.3 Bi-Level Stochastic Optimization Model

In order to determine the pre-disaster investment plan, a bi-level discrete stochastic model is developed to holistically address the pre-disaster investment planning problem based on the various link significance factors. The upper level of the bi-level model seeks an investment strategy to upgrade links in the pre-disaster stage such that the network survivability is enhanced. It is subject to the constraint on investment budget, and is impacted by the flow x which results in the expected shortest response time over the surviving network set in the lower level. Therefore, the solution to the model is a link investment strategy in the pre-disaster stage so that the expected response time in the surviving network under multiple disaster scenarios is minimized. Mathematically, the bi-level stochastic optimization model P is represented as:

$$ \begin{array}{ll}P\hfill & Max\ {\displaystyle {\sum}_{\left[i,j\right]\in E}\left({W}_{ij}^f\left({x}_{ij}\right)+{W}_{ij}^c\left({y}_{ij},{\xi}^s\right)+{W}_{ij}^p\left({y}_{ij}\right)\right)}{y}_{ij}\hfill \end{array} $$

(10)

$$ \begin{array}{ll}s.t.\hfill & {\displaystyle {\sum}_{\left[i,j\right]\in E}{c}_{ij}{y}_{ij}}\le b\hfill \end{array} $$

(11)

$$ 0\le {y}_{ij}\le 1\kern1em \left[i,j\right]\mathit{\in}E $$

(12)

$$ x\in argmi{n}_x\left\{F(x)={\displaystyle {\sum}_{\omega_d\in \varOmega}\varGamma \left({\omega}_d\right)}\left[{\displaystyle {\sum}_{\xi^s\in \varXi }f\left(x\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)\right)P\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)}\right]\right\} $$

(13)

$$ \begin{array}{ll}s.t.\kern1em {x}_{ij}^k\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)=0\; or\;1\hfill & \mathit{\forall}\left[i,j\right]\mathit{\in}E,\kern0.5em \mathit{\forall}k\kern0.5em \mathit{\in}K,\kern0.5em \mathit{\forall}{\xi}^s\kern0.5em \mathit{\in}\varXi, {\omega}_d\kern0.5em \mathit{\in}\varOmega \hfill \end{array} $$

(14)

$$ {x}_{ij}^k\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)\le \left.{\xi}_{ij}^s\right|\left(y,{\omega}_d\right)\kern1.75em \mathit{\forall}\left[i,j\right]\mathit{\in}E,\kern0.5em \mathit{\forall}k\kern0.5em \mathit{\in}K,\kern0.5em \mathit{\forall}{\xi}^s\kern0.5em \in \varXi, {\omega}_d\kern0.5em \mathit{\in}\varOmega \kern0.5em $$

(15)

$$ \begin{array}{r}\hfill {\displaystyle {\sum}_{j\in N}{x}_{ij}^k\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)}-{\displaystyle {\sum}_{j\in N}{x}_{ji}^k\left(\left.{\xi}^s\right|\left(y,{\omega}_d\right)\right)}=\left\{\begin{array}{c}\hfill 1,\kern0.5em if\kern0.5em i=O(k)\hfill \\ {}\hfill -1,\kern0.5em if\kern0.5em i=D(k)\hfill \\ {}\hfill 0,\kern0.5em otherwise\hfill \end{array}\right.\\ {}\hfill \forall i\in N,\forall k\in K,\forall {\xi}^s\in \varXi, {\omega}_d\kern0.5em \mathit{\in}\varOmega \kern0.5em \end{array} $$

(16)

In model P, Eq. (10) is the objective function in the upper level, which maximizes the benefits to network survivability (related to response time performance) in terms of the three factors discussed in the previous section, through link investments. Namely, a link with higher contribution to response time reduction in the surviving networks may obtain more investment so that the value of the objective function can be maximized. While Eq. (10) weighs the three factors equally, Section 6.2.3 performs sensitivity analyses to explore the relative significance of each factor to the solution method. Equation (11) represents the budget constraint. Equation (12) defines the continuous decision variables, and Eq. (13) constrains the flow of the surviving network in the lower level such that it results in the expected shortest response time of the surviving networks under the given investment strategy. The expected shortest response time F(x) is measured by the expected shortest travel time across all O-D pairs under all possible disaster scenarios. Equations (1) and (3) provide the expressions to compute the key components P(ξ^s|(y,ω_d)) and f(x(ξ^s|(y,ω_d))) in F(x), respectively. Equation (14) represents the binary 0-1 variable that indicates the existence of response flow on the individual links. Equation (15) further guarantees that the feasible flow only appears on the surviving links. Equation (16) illustrates the node flow conservation based on one unit of flow being transported for each O-D pair. As discussed earlier, the shortest paths are based on link free-flow travel times.

The two levels are holistically linked by the strategic investment vector  y which represents the decision variables in the upper level, and the flow vector  x which represents the decision variables in the lower level. This illustrates that the optimal link investment plan in the upper level is based on the link importance to response time reduction, which is dependent on the flow x resulting from the lower level. Correspondingly, the optimal network performance at the lower level is evaluated under the given surviving networks which depend on the investment strategy y in the upper level. Hence, these dependencies involving x and y demonstrate that the interactions between the pre-disaster investment planning and the post-disaster network performance occur in both directions.

4 Solution Algorithm

This study proposes a heuristic algorithm to solve the bi-level optimization model provided above. A bi-level optimization model is intrinsically difficult to solve (Farvaresh and Sepehri 2013); even the linear-to-linear bi-level problem is NP-hard (Jeroslow 1985). Considering the inherent complexity of the problem, this study seeks “good” feasible solutions within a reasonable computational time by using an iterative procedure combined with Monte Carlo simulation (Shapiro 2001). More specifically, based on the structural characteristics of the bi-level model P, the proposed heuristic algorithm decomposes model P into two separate models addressed in two stages: a linear program P1 for the pre-disaster investment decision problem, and a shortest path problem P2 for the post-disaster network performance problem. The Monte Carlo simulation is embedded into the second stage to sample the possible surviving networks under multiple disasters. A fixed point, representing the feasible solution of model P, is searched for iteratively by solving models P1 and P2 in the two stages. The proposed algorithm is labeled the Two-Stage Heuristic Algorithm (TSHA) hereafter. Models P1 and P2 are as follows:

$$ \begin{array}{l}\begin{array}{ll}P1\hfill & Max\;F\left({y}^{\prime}\right)={\displaystyle {\sum}_{\left[i,j\right]\in E}\left({W}_{ij}^f\left(\left.x\right|{y}^{v-1}\right)+{W}_{ij}^c\left({y}_{ij}^{v-1},\left.{\xi}^s\right|{y}^{v-1}\right)+{W}_{ij}^p\left({y}^{v-1}\right)\right)}{y}_{ij}^{\prime}\hfill \end{array}\hfill \\ {}\begin{array}{ll}s.t.\hfill & {\displaystyle {\sum}_{\left[i,j\right]\in E}{c}_{ij}{y}_{ij}^{\prime}\le b}\hfill \end{array}\hfill \\ {}\begin{array}{ll}\hfill & {y}_{ij}^{\prime}\ge 0\kern1em \forall \left[i,j\right]\in E\hfill \end{array}\hfill \\ {}\begin{array}{ll}\hfill & {y}_{ij}^{\prime}\le 1\kern1em \forall \left[i,j\right]\in E\hfill \end{array}\hfill \\ {}\begin{array}{ll}P 2\hfill & Min\;F(x)={\displaystyle {\sum}_{\omega_d\in \varOmega}\varGamma \left({\omega}_d\right)}\left[{\displaystyle {\sum}_{\xi^s\in \varXi }f\left(x\left(\left.{\xi}^s\right|\left({y}^v,{\omega}_d\right)\right)\right)P\left(\left.{\xi}^s\right|\left({y}^v,{\omega}_d\right)\right)}\right]\hfill \end{array}\hfill \\ {}\begin{array}{ll}s.t.\hfill & {x}_{ij}^k\left(\left.{\xi}^s\right|\left({y}^v,{\omega}_d\right)\right)\le \left.{\xi}_{ij}^s\right|\left({y}^v,{\omega}_d\right)\kern1em \forall \left[i,j\right]\kern1.25em \in N,\forall k\in K,\forall {\xi}^s\in \varXi, {\omega}_d\kern0.5em \mathit{\in}\varOmega \kern0.5em \hfill \end{array}\hfill \\ {}\begin{array}{ll}\hfill & {x}_{ij}^k\left({\xi}^s\Big|\left({y}^v,{\omega}_d\right)\right)=0\ or\ 1\kern2em \hfill \end{array}\kern1em \forall \left[i,j\right]\kern1em \in N,\forall k\in K,\forall {\xi}^s\in \varXi, {\omega}_d\kern0.5em \mathit{\in}\varOmega \hfill \\ {}\begin{array}{ll}\hfill & {\displaystyle {\sum}_{j\in N}{x}_{ij}^k}\left(\left.{\xi}^s\right|\left({y}^v,{\omega}_d\right)\right)-{\displaystyle {\sum}_{j\in N}{x}_{ji}^k\left(\left.{\xi}^s\right|\left({y}^v,{\omega}_d\right)\right)}=\left\{\begin{array}{c}\hfill 1,\kern0.5em if\kern0.5em i=O(k)\hfill \\ {}\hfill -1,\kern0.5em if\kern0.5em i=D(k)\hfill \\ {}\hfill 0, otherwise\hfill \end{array}\right.\hfill \end{array}\hfill \\ {}\begin{array}{rrr}\hfill & \hfill & \hfill \kern13em \forall i\in N,\forall k\in K,\forall {\xi}^s\in \varXi, {\omega}_d\mathit{\in}\varOmega \end{array}\hfill \end{array} $$

The solution search process of the TSHA is as follows. First, the TSHA solves model P1 and obtains the optimal investment decision  y′ given that  W ^f, W ^p, and W ^c are determined based on the investment decisions and flows from the previous iteration v − 1 (where v is the notation for iteration). Then, the investment decision y^v at the current iteration is obtained by combining y′ with y^v − 1 using the Method of Successive Averages (MSA); that is, ${y}^v=\frac{1}{v}{y}^{\prime }+\frac{\left(v-1\right)}{v}{y}^{v-1}$. Since the feasible region of model P1 is a convex set, the investment strategy resulting from MSA will retain feasibility. The numerical experiments in the next section demonstrate that the MSA procedure retains the good qualities of the solutions obtained in previous iterations and also boosts the convergence of the proposed algorithm.

Next, given investment decision y^v, the TSHA solves model P2 to determine the flow pattern which results in the expected shortest response time between O-D pairs in the surviving networks (sampled by Monte Carlo Simulation) under various disasters. The flow x obtained in the second stage is used in the next iteration to update  W ^f, W ^p, and W ^c. This two-stage iterative process is repeated until a fixed point (x ^∗, y ^∗) is obtained that is consistent with the convergence criterion used. The two stages of the proposed algorithm are linked by the investment strategy y in the first stage and the flow vector x in the second stage. The iterative process is consistent with the proposed approach to systematically consider the pre-disaster investment strategy and the post-disaster network performance in both directions.

Note that y ^∗ represents a feasible investment solution of the proposed bi-level stochastic optimization model, which results in the network performance F(x ^∗), though (x ^∗, y ^∗) together may not represent a feasible solution for model P as x ^∗ and y ^∗ are obtained at different levels of the iterative TSHA. However, based on the convergence criterion, (x ^∗, y ^∗) can be viewed as a feasible solution for P within an acceptable tolerance level (in our experiments, the difference between the solutions in five successive iterations is within a pre-specified threshold Δ). As the primary study focus is to find an effective investment plan y, the TSHA can solve the proposed pre-disaster investment planning problem to provide a “good” solution in a computationally efficient manner.

5 Numerical Experiments

5.1 Experimental Setup

This section applies the proposed bi-level stochastic optimization model P and the solution algorithm TSHA to the Sioux Falls city network (shown in Fig. 1) which includes 24 nodes and 76 links. The case study demonstrates the practical applicability of the proposed approach, and also illustrates the efficiency of the proposed algorithm.

Fig. 1

Sioux Falls city network

Due to the lack of field data, the following input data are generated for the experiments: (i) the O-D pairs: (14, 7), (12, 18), (4, 8), (9, 7) and (14, 20); (ii) c_ij: full link upgrade cost; accordingly, the full upgradation budget B = ∑ c_ij; (iii) t_ij: free flow link travel time in minutes; and (iv) cp_ij: link traffic flow capacity, which is estimated using service volumes of multilane highways for LOS C (Exhibit 12-5 in Highway Capacity Manual, 2000). Further, we also randomly generate the following necessary parameters for each experiment: (i) α_k: the weight for O-D pair k; k = 5; (ii) Γ(ω_d): the occurrence probabilities of ten different disaster scenarios; (iii) p_ij(ω_d): the probability of link failure in a disaster if it is not upgraded; and (iv) q_ij(ω_d): the probability of link [i, j] failure in a disaster if it is fully upgraded.

The surviving networks are sampled using Monte Carlo simulation as follows. First, the surviving links are sampled. A random value λ _ij is generated to represent the randomness of the link failure; link [i, j] fails if λ _ij  ≤ θ _ij (link failure probability θ_ij defined in Section 3.1), otherwise it survives. Second, the surviving network pool is sampled. Under a disaster, a surviving network consists of all the surviving links. For the given link survivable probabilities under a disaster, a thousand surviving networks are randomly generated. They are used as the sample pool to evaluate the post-disaster performance (response time between O-D pairs). The experimental results illustrate that a sample of a thousand surviving networks is a sufficient sample size for the network used in this case study.

5.2 Experiments and Results

The experiments investigate the characteristics of the proposed bi-level stochastic optimization model and its solution algorithm.

5.2.1 Convergence and Computation Performance

The convergence of the TSHA solution algorithm is analyzed using a relatively tight convergence criterion, that |y _v  − y _v − 1|² ≤ Δ for five consecutive iterations; that is, the search procedure will not terminate until the difference between the investment solutions in two successive iterations is less than Δ for five consecutive iterations. The Δ values used in the experiments are: 0.5, 0.2, 0.05, 0.01, 0.005, and 0.001. In addition, for each Δ, we test the convergence of the algorithm under different budget plans, r = 0.1, 0.2, 0.3, 0.4, 0. 5 and 0.8.

The results are illustrated in Fig. 2, with Fig. 2 and b illustrating the convergence trajectories of the algorithm under different budget plans for Δ = 0.5 and Δ = 0.01, respectively. Figure 2c illustrates the relationship between F(x), the expected shortest response time of the surviving networks across O-D pairs over all tested disasters, and the convergent criterion Δ under the different budget plans. Both Fig. 2a (Δ = 0.5) and b (Δ = 0.01) indicate that the proposed algorithm efficiently converges to a fixed point under various budget plans r. Further, the algorithm needs more iterations to converge under a tighter convergence criterion (Fig. 2a (Δ = 0.5) needs less number of iterations to converge than Fig. 2b (Δ = 0.01)), but results in a better solution; that is, a smaller value of F(x) (the converged F(x) values in Fig. 2b (Δ = 0.01) are less than the corresponding F(x) values in Fig. 2a (Δ = 0.5)). However, Fig. 2c indicates that the improvement of F(x) is very limited after Δ is less than 0.01 under each budget plan. It indicates that the performance of the algorithm trends to a plateau at this point. Therefore, Δ = 0.01 is adopted in the subsequent experiments for the convergence criterion. Further, the results indicate that a very tight convergence condition is not necessary, and that the decision-maker may apply this insight to avoid a focused pursuit of a high convergence condition and save computation cost.

Fig. 2

Analysis of convergence. a Convergence of the algorithm under various budgets and Δ = 0.5. b Convergence of the algorithm under various budgets and Δ = 0.01. c F(x) under various budgets and Δ values

Equally important, we observe that larger investment budgets (a larger  r) enlarge the feasible solution space. Correspondingly, more iterations are required to converge, as seen in Fig. 2a and b. Further, a higher budget will always lead to a better investment decision in terms of F(x). However, the marginal improvement is not significant beyond r = 0.3, as seen in Fig. 2c where under each convergence condition, improving budget plans from r = 0.3 to r = 0.4, 0.5, or even 0.8, does not lead to a significant improvement in F(x). Hence, the proposed methodology can provide useful insights to decision-makers to aid them in identifying an efficient budget plan. That is, decision-makers can test different investment rates and find the preferred one (such as r = 0.3 in our experiments) beyond which the marginal improvement is less significant.

From a computational standpoint, both P1 in the first stage and P2 in the second stage can be solved using existing polynomial time (or efficient) algorithms in the literature since P1 is a linear program and P2 is a shortest path problem in the surviving network. The most computationally intensive component of the proposed solution algorithm is the iterative process to search for the fixed point in the feasible solution space, which increases with the network size. This is a standard characteristic of most such combination optimization problems. Specific to this study, we found that embedding the MSA procedure in the search process can efficiently reduce the convergence time. In the study experiments, using Matlab R2011a on a computer with 3.25GB RAM and Intel(R) Core(TM)2 Duo CPU E8200@2.66GHz, it takes about 17 min of execution time, on average, to converge to an acceptable solution under the convergence criterion Δ = 0.01. As the proposed approach is used to addresses a long-term pre-disaster (off-line) investment planning problem, the computational time is not a tight constraint and does not represent a key barrier to using the proposed methodology for large networks.

The solution of the proposed TSHA algorithm may potentially depend on the starting point as it is an iterative procedure. However, this effect does not manifest in the study experiments. More importantly, specific to the proposed problem, a natural starting point is to set all investment decision variables equal to zero as it corresponds to the current infrastructure network condition, with none of the links invested in. It enables the proposed methodology to be consistent with the real-world decision process as the pre-disaster investment planning usually uses the current network infrastructure conditions for future investment decisions. Hence, the proposed starting point for the solution algorithm is synergistic with the application of the proposed methodology in practice.

5.2.2 Quality of the Solution

This section explores the quality of the feasible investment solution y. To do so, consider an expected surviving network Π, in which the links are considered to survive in disasters if their expected link survival probabilities ${\overline{\theta}}_{ij}$ are greater than a threshold Θ corresponding to the level of disaster severity. Mathematically, ${\overline{\theta}}_{ij}$ and Π are defined by Eqs. (17) and (18), respectively.

$$ {\overline{\theta}}_{ij}={\displaystyle {\sum}_d\Gamma \left({\omega}_d\right)\left(1-{p}_{ij}\left({\omega}_d\right)+{y}_{ij}\left({p}_{ij}\left({\omega}_d\right)-{q}_{ij}\left({\omega}_d\right)\right)\right)} $$

(17)

$$ \varPi ={\left\{{\pi}_{ij}\right\}}^{\left|E\right|},{\pi}_{ij}=\left\{\begin{array}{c}\hfill 1,{\overline{\theta}}_{ij}\ge \varTheta \hfill \\ {}\hfill 0,{\overline{\theta}}_{ij}<\varTheta\ \hfill \end{array}\right. $$

(18)

Correspondingly, the weighted shortest response time of the expected surviving network Π over all O-D pairs is denoted as Φ(x), which is computed using Eq. (19):

$$ \varPhi (x)={\displaystyle {\sum}_{k=1}^K{\alpha}_k{g}_k\left({x}_{ij}^k\left(\varPi \right)\right)} $$

(19)

where g _k (x ^k _ij (Π)) is the shortest response time for an O-D pair k in Π.

From the definitions of Π and Θ, it can be noted that: (i) Π may not belong to any individual surviving network in {ξ^s}^|Ξ| under individual disasters since it results from the expected link survivability distribution $\left\{{\overline{\theta}}_{ij}\right\}$, which is different from the link survivability distribution under a specific disaster; (ii) Π represents an average scenario of the surviving networks over all disasters, and its performance (such as the shortest response time Φ(x) in this study) demonstrates the average survivability or functionality of the surviving networks over all disasters; and (iii) The disaster severity is implied by the threshold Θ that is linked to link survival probabilities. A larger value of Θ implies a higher threshold for a link to survive under a disaster. For example, Θ = 0.8 indicates that only if the expected link survival probability is higher than 0.8, the link will survive, otherwise it fails. Thus, a higher Θ value indicates a more severe disaster which may result in fewer surviving links in Π, and vice versa.

Based on the above observations, the Φ(x)s under different disaster severities Θs are used as benchmarks to evaluate the quality of investment solution y from the THSA. The underlying idea is that the network performance F(x) predicted by the proposed bi-level optimization model is compared to the average network performances represented by the Φ(x)s given that the network links are upgraded using investment solution y obtained from the bi-level optimization model. The objective is to analyze whether the predicted network performance F(x) is better or worse than the Φ(x)s under the disaster with the same severity. This is done using the following sequential steps: (1) By solving model P, obtain an investment solution y and the expected network performance F(x); (2) Using this investment solution y, determine the expected surviving network Π under disaster severity Θ; and (iii) Compute the shortest network response time Φ(x) of Π under each disaster severity. The quality of the investment solution y is demonstrated by comparing F(x) to the Φ(x)s. To facilitate the discussion hereafter, we more specifically refer to Φ(x) as Φ(x|Π(Θ)), and F(x) as F(x|Ξ).

The experiment results illustrated in Fig. 3 indicate that F(x|Ξ) predicts the Φ(x|Π(Θ))s reasonably well under disasters of moderate severity (such as Θ = 0.6 and 0.7), but underestimates or overestimates Φ(x|Π(Θ))s under disasters of high severity (Θ = 0.8) or mild severity (Θ = 0.5), respectively. This is especially perceptible under disasters of very mild severity. Through these observations, the applicability of the proposed approach is articulated as follows. First, decision-makers addressing pre-disaster investment decisions can apply the proposed bi-level model and the associated solution algorithm to generate an investment strategy, and robustly predict the average network performance for moderately severe disasters. Second, the proposed approach is also relevant for very severe disaster scenarios, since the approaches will result in an investment plan leading to better average network performance. Third, for very mild disasters, the proposed approach would lead to a predicted network performance higher than the target average network performance. Hence, the proposed approach is meaningful under different disaster levels. Further, the focus of pre-disaster investment planning is typically in the moderately severe disaster context as highly severe disasters usually occur with very low frequencies but require unacceptable levels of expenditures to strengthen against them, and mildly severe disasters occur more often but cause insignificant damage. By contrast, moderately severe disasters usually result in considerable damage and occur reasonably frequently. Thereby, adopting an acceptable budget and a strategic investment plan can result in significant improvements in network performance under such moderately severe disasters. Hence, the proposed method aids in the investment decision-making process for effective pre-disaster investment planning.

Fig. 3

Comparison of F(x|Ξ) and Φ(x|Π)s under disasters of various severities Θ

5.2.3 Significance of W ^c, W ^f and W ^p

Next, the significance of the three W factors: W ^c, W ^f, and W ^p which are used to identify the importance of a link for pre-disaster investment planning, is investigated. By comparing their mathematical expressions (Eqs. (4)–(9)), some preliminary insights are provided as follows. Both W ^f and W ^c are impacted by the investment decision in the upper level as well as the flow in the lower level of the bi-level model. Hence, they bridge the two levels of the proposed bi-level model as well as the two stages in the TSHA algorithm, and can potentially guide the TSHA to a good solution. By contrast, W ^p  is dependent only on the decision variable y in the upper level; hence, it does not represent a direct linkage between the upper and the lower levels of the model. Correspondingly, W ^p  by itself cannot guide the interactive solution search process in the TSHA. Therefore, we do not discuss the effect of W ^p by itself on the solution search process.

Several questions arise related to the significance of the three W factors when viewed from a more holistic perspective: (i) is W ^c or W ^f more significant?, (ii) what is the effect if W ^c, W ^f, and W ^p are factored in the different combinations thereof?, and (iii) is it always necessary to include all three factors? These questions are addressed hereafter based on the results of the corresponding experiments.

The relevant experiments consist of four cases, which differ in terms of the sets of O-D pairs considered (two different sets, including the set identified in Section 6.1) and the link failure probability distributions used (two sets of randomly-generated link failure distributions for each O-D pair). For each case, the six different budget plans (r = 0.1, 0.2, 0.3, 0.4, 0.5 and 0.8) are applied, but the optimal investment strategies are searched using different combinations of  W ^c, W ^f, and W ^p. The results are illustrated in Fig. 4 for each case, by plotting the relationship between the network performance, F(x), and the different combinations of  W ^c, W ^f, and W ^p for each budget plan. In the figures, a point with “*” indicates the best network performance under that budget plan in the corresponding case, and a point with a “♦” symbol represents a value very close to the best network performance. We differentiate these points to illustrate this aspect.

Fig. 4

Analysis of the W factors

The results indicate that incorporating the effect of only W ^f in the pre-disaster investment decision strategy usually results in a better network performance than factoring only W ^c. This is illustrated in Fig. 4 for the four cases; F(x) values for the scenarios factoring only W ^f are in most instances smaller than those considering only W ^c. However, there are exceptions to this trend as illustrated in the figure.

For the scenarios in which W ^f (or W ^c) is already involved, by additionally considering W ^c (or W ^f) it may be possible to slightly improve the solution in some instances. For example, Case 1 in Fig. 4 illustrates that factoring both W ^f and W ^c results in smaller F(x) values than when only one of them is considered, for budget plans r =0.4, 0.5, and 0.8. The same can be observed in Case 2 when r = 0.2, 0.3, 0.5, and in Case 3 when r = 0.1. These observations can provide decision-makers insights on the complexity of the interactions among traffic flow, network connectivity, and investment plan. Hence, it is meaningful to consider their effects in an integrated manner.

Some results indicate that W ^p can also improve the solution if W ^f is already involved, but this usually occurs when the budget is relatively tight. This is illustrated in Case 1 and Case 4 where the best solution appears at the combination of W ^f and W ^p when the budget plan is r = 0.1. The inclusion of W ^p beyond considering W ^c only does not lead to benefits in these experiments.

The results illustrate that the best solutions may occur under different combinations of  W ^c, W ^f, and W ^p under different budget plans. For instance, in Case 1, W ^p combined with W ^f results in the best solution under the budget plan r = 0.1. In Case 2, using  W ^c only results in the best solution under the budget plan r = 0.4. Further, the consideration of W ^c, W ^f, and W ^p together results in the best solution in Case 1 under the budget plan r = 0.3. In Case 4, under the budget plan r =0.3, 0.4, 0.5, 0.8, most often, the best solutions will occur under W ^f only or the combination of W ^f and W ^c.

In summary, the three factors W ^c, W ^f, and W ^p, are significant to determining a strategic pre-disaster investment decision. More importantly, the effects of  W ^f, W ^c, W ^p, and the combinations thereof on the solution are influenced by the budget plan, the network structure, O-D pairs of interest, the distributions of the link survival probabilities, and the link upgrade costs. Hence, for a given network structure and budget plan, the study insights suggest that the decision-maker/practitioners should holistically analyze different combinations of the three W  factors to explore the best pre-disaster investment strategy.

5.2.4 Sensitivity Analyses for the Weights of W ^c, W ^f and W ^p

Next, the relative significance of each W factor (weighted identically in Eq. (10)) is explored. To do so, the bi-level optimization model P is solved using the TSHA, in which one of the weights of the three W factors is increased from 1 to 100 with the step size 10, while keeping the weights of the other two W factors equal to 1. The results shown in Fig. 5 indicate that under the different budget plans, increasing the weight of W ^c, W ^f or W ^p individually does not improve the solution. They suggest that focus on a single factor among network connectivity, traffic flow usage, and upgradation cost may lead to a worse investment strategy for pre-disaster planning. In other words, if practitioners overemphasize the importance of only connectivity (or only traffic flow usage or upgradation cost) and invest in the upgradation of the corresponding links, it may lead to a worse post-disaster response time.

Fig. 5

Sensitivity analysis for the weights of the W factors

5.2.5 Sensitivity Analyses for the Weights of W ^c1 and W ^c2

This section analyzes the relative importance of W ^c1 and W ^c2, which were weighted identically in Eq. (4). To do so, we re-write the formulation of W ^c as:

$$ {W}_{ij}^c=\left(1-\mu \right){W}_{ij}^{c1}+\mu {W}_{ij}^{c2} $$

(20)

where μ increases from 0 to 1 with step size 0.1. Hence, if the weight of W ^c2 _ij is increased from 0 to 1, then the weight of W ^c1 _ij is correspondingly decreased from 1 to 0. The relevant experiments also include the four cases identified in Section 6.2.3, which differ in terms of the sets of O-D pairs considered and the link failure probability distributions used.

Figure 6 illustrates the experiment results, where * on the x axis represents the solution obtained by weighting W ^c1 and W ^c2 evenly. The results indicate that a better investment strategy can be obtained by treating W ^c1 and W ^c2 evenly (assigning both of them a weight equal to 1) rather than overweighing either W ^c1 or W ^c2 in W ^c. This implies that in the study experiments, neither significant deterministic single link failure nor stochastic link set failure directs the proposed methodology to identify a link set whose upgradation leads to a better network performance in terms of response time under disasters. Thereby, decision-makers and practitioners may need to treat W ^c1 and W ^c2 evenly in evaluating the link significance for network connectivity in certain applications.

Fig. 6

Sensitivity analysis for the weights of W ^c1 and W ^c2

Overall, the results in Sections 6.2.4 and 6.2.5 provide decision-makers/practitioners insights and guidelines on how to: (i) assign weights to the three W factors to evaluate the link significance to post-disaster response time, and (ii) allocate the investment budget. They further reinforce the idea proposed in this study that decision-makers need to holistically analyze the impacts of different factors rather than focusing on only one of them.

6 Concluding Comments

This study proposes a bi-level stochastic optimization model to address the pre-disaster investment planning problem that seeks to enhance network survivability to reduce the post-disaster expected response time for the surviving networks under different disaster scenarios. To our knowledge, this represents the first instance that two levels of stochasticity, link failure and disaster characteristics, are being explicitly incorporated in the same framework for this problem context. Due to the complexity of the model, a two-stage heuristic algorithm, TSHA, is proposed which decomposes the bi-level optimization model into two models: a linear optimization model and an expected shortest path model. The two models are solved in two separate, but interacting, stages. By iteratively solving the two models until the solution satisfies the pre-defined convergence criterion, the algorithm determines a fixed point which represents a feasible solution within an acceptable tolerance level for the proposed bi-level stochastic optimization model.

The results from the numerical experiments suggest that the TSHA algorithm can efficiently converge to a feasible solution for the proposed bi-level stochastic optimization model. More importantly, our experiments illustrate that the marginal improvement of network performance does not always increase with budget increment. Thereby, the proposed methodology can provide insights for decision-makers to identify an efficient budget plan and the optimal link investment strategy by systematically considering the interactions between the pre-disaster investment decisions and the post-disaster network performance. Further, the proposed bi-level optimization model predicts the network performance robustly under disasters of moderate severity.

In the parametric analyses, this study considers three factors, W ^c, W ^f, and W ^p. They represent the significance of the network connectivity, traffic flow and marginal link survivability improvement on the investment decisions, respectively. More precisely, they illustrate the effect of the network structure, traffic demand distribution, and upgradation costs on the investment strategy in the pre-disaster investment planning. These factors are often considered separately or in isolation; the parametric analyses suggest the need for the decision-maker to use a holistic perspective to capture the influence of these factors. Omitting any of them may lead to gaps in the planning strategy. Further, the relative significance of these factors varies with budget limits, link survival characteristics, and surviving network topologies. These results indicate that there is no single solution that “fits” all cases effectively. Hence, the decision-maker may benefit from considering all possible combinations of these factors and analyze them under different budget plans to identify the best solution for the pre-disaster investment strategy in a specific case. The proposed approach provides the capability for decision-makers to conduct the aforementioned comprehensive analyses.

Based on the perspective in this study that the network performance implies the response travel time for the response resources (such as personnel and equipment), traffic flow congestion is not considered on the network links, and free flow travel times are assumed. While this may suffice for the immediate post-disaster response, there is a need to factor the traffic patterns when addressing medium- and long-term post-disaster recovery and reconstruction. This represents a future research direction. It also has the potential to further refine the understanding of the significance of the various W factors. Correspondingly, further research work incorporating the issues of traffic congestion, dynamic travel times, and the possibility of surviving links with partial functionality, represents an on-going effort.