1 Introduction

Networked infrastructures are continually at risk of service disruption due to environmental, technological or intentional damage to system components. Natural disasters, such as hurricanes, floods and earthquakes, can have an extensive geographic range of impact, rendering considerable portions of transportation and utility networks inoperable. The effects of hurricane Katrina on the U.S. Gulf Coast, as an example, illustrate that widespread infrastructure-based disruption can arise from such events. In less dramatic cases, such as the December 2006 earthquake off the coast of Taiwan, key components of a network can be impacted, severely limiting the performance of infrastructure systems (CNN 2006; Kitamura et al. 2007). Unexpected events that are smaller in geographic scope can also cause significant damage because their impacts can radiate through a system, resulting in cascading failure of facilities and loss of service. For instance, the initial loss of a single electrical generation plant in Ohio led to widespread facility failure in the 2003 blackout of the Northeastern portion of the U.S. power grid (USCA 2004; Grubesic and Murray 2006). More recently, both the failure of a disconnect switch and the subsequent fire in an electrical substation west of Miami resulted in nearly three million customers losing power throughout Florida (CNN 2008c). Similarly, structural failures, accidents, as well as seemingly innocuous events, such as construction or the dropping of a ship’s anchor, can disrupt service and require time-consuming repair efforts (CGA 2005; CNN 2008a, b). Although accidents and natural disasters are always a concern, other more sinister threats oriented at maximizing infrastructure damage, such as terrorism and acts of war, add additional potential for system disruption (USCOTA 1990). For instance, a major threat to networks heavily reliant on electrical components is a High Altitude Electromagnetic Pulse (HEMP) attack. A HEMP insult consists of discharging a nuclear weapon high above the earth’s surface in an effort to generate an intense electromagnetic pulse. The resulting electromagnetic field has the potential to debilitate electrical, computer and telecommunications equipment over an extremely large area (Foster et al. 2004). For example, in the early 1960s, the United States conducted a high altitude nuclear test over the Pacific Ocean and the resulting electromagnetic pulse disrupted electronic equipment and radio communications 800 miles away in Hawaii (Wilson 2004). In this context, it is believed that a single detonation over Kansas has the potential to impact electronic equipment throughout the continental U.S (FAS 2009).

While fortifying or hardening networked infrastructure against such unexpected events is an appealing, proactive planning goal, such options are costly and may not always be available or effective in preventing infrastructure losses. Thus, planning efforts are necessary for ensuring that response plans are in place to guide the restoration of disrupted services. Although the geographic scale of infrastructure damage is highly variable, most extreme events yield massive damage. As a result, planning agencies are faced with the task of efficiently coordinating facility repair in order to restore service to those in need in a timely and efficient manner. Unfortunately, complete recovery of a network is often delayed due to workforce and budget limitations, so the allocation of resources must be prioritized. In an effort to address this complex planning problem, this paper introduces a spatial optimization model that provides a methodological framework for developing and evaluating network restoration contingencies.

We begin with a review of previous efforts to model the recovery of disrupted systems. As is discussed, there are many considerations that may be of interest in recovery planning. One theme that emerges in particular is the importance of restoring origin-destination (O-D) connectivity/flow in an efficient manner (Meshkovskiy and Rokotyan 1992). To further explore the complicated nature of infrastructure recovery, a multi-objective recovery model is proposed for identifying tradeoffs between flow restoration and system cost over time. Analysis of a telecommunications network illustrates the tradeoffs between restoration objectives and the value of the proposed model.

2 Background

There are many facets, both theoretical and methodological, to the study of disruptive events and their repercussions on infrastructure and socio-economic systems. The focus of this paper, infrastructure recovery, constitutes one important aspect of the lifecycle of a damaging event or disaster (see Smith et al. 1994; Baker et al. 2004; Altay and Green 2006). With respect to networked infrastructures, recovery efforts are typically centered on restoring system performance to pre-disruption status. In many cases, damaged network components cannot be simultaneously repaired to reestablish normal service. Also, the lack of budgetary resources often limits the extent of restoration efforts. It is therefore necessary that contingencies associated with various recovery plans are evaluated to determine what actions and associated outcomes best fit the planning goals and budget of an organization. One way of assessing effectiveness of recovery efforts is through the evaluation of system performance relative to pre-disruption operation (Chen and Tzeng 1999; Chang and Nojima 2001). A recovery plan that maximizes system performance while conforming to resource limitations governing the recovery effort is certainly desirable. However, thousands, millions, or more recovery plan options can exist for any network disruption. As a result, the recovery problem becomes one of evaluating and selecting between alternatives.

Various approaches have been proposed to address the basic problem of optimal utilization of resources for reestablishing network service. For example, Meshkovskiy and Rokotyan (1992) note the importance of restoring network connectivity following a disaster involving the loss of a substantial portion of a network. In particular, they address the case where insufficient restoration equipment exists to completely restore network connectivity. The problem is viewed as a Steiner tree and a solution heuristic is proposed to restore connectivity to a set of high-priority nodes (as defined beforehand) at minimal cost. Sarker et al. (1996) address the problem of siting housing crews for efficient response to disruptions in electrical power distribution systems. To do this, they represent the regional electrical distribution system as a set of cells, with each displaying varying levels of demand. A quadratic, mixed-integer formulation is proposed to site response crews such that the transportation costs associated with repair are minimized. Chen and Tzeng (1999) propose a multi-objective bi-level optimization model for identifying restoration plans that minimize total repair time, transportation costs and down time between projects. A genetic algorithm is outlined for identifying solutions to their model. Cho et al. (2000) investigate a heuristic approach to restoring earthquake damaged highway infrastructure. Their approach involves assigning damaged network components to spatial clusters in order to facilitate staging of restoration equipment and crews. The clusters are then “repaired” to pre-disruption traffic volumes. In other work, Ambs et al. (2000) propose a linear program for adding capacity in order to ensure effective service restoration in the event of the loss of a single network arc. Bryson et al. (2002) developed a mixed integer programming approach for selecting a set of recovery subplans giving the greatest benefit to business operation. Casari and Wilkie (2005) discuss restoration when multiple infrastructures, operated by different firms, are involved. Lee and Kim (2007) detail an approach for identifying reconstruction strategies that minimize both total repair time and economic losses over the course of reconstruction subject to budgetary constraints in each repair period. A genetic algorithm is proposed to find feasible strategies and evaluate them with respect to the model objectives. Lee et al. (2007) focus on a different case of network restoration, that of selecting the location of temporary arcs (e.g., shunts) needed to completely reestablish network services over a set of interdependent networks. A mixed-integer optimization model is proposed to minimize the operating costs involved in temporary emergency restoration. However, prioritizing restoration of damaged infrastructure is not addressed.

The problem of network restoration is also closely related to that of network maintenance/rehabilitation project scheduling (see Kiyota et al. 1999; Bonyuet et al. 2002; Wang et al. 2003; Madanat et al. 2006). In such problems, the task is to decide which network arcs to rehabilitate or upgrade to optimize user benefit/cost. Although restoration and maintenance/improvement scheduling do share some similarities, they are fundamentally different since service maintenance/improvement assumes system connectivity whereas this condition may not hold in damaged infrastructure. Another related class of network design models has an objective of minimizing the cost associated with locating and installing spare capacity in a network to facilitate restoration after damage to a network (see Balakrishnan et al. 2001, 2002).

In a much different context, that of network vulnerability assessment, connectivity is a condition that is explicitly accounted for (Murray et al. 2007; Matisziw et al. 2009). Models have been proposed to identify the worst-case scenario of connectivity/flow loss given some pre-specified level of damage to the network. Models have also been developed to identify the scenario(s) involving the least amount of connectivity/flow loss given some pre-specified level of network damage (see Matisziw et al. 2007; Murray et al. 2007; Matisziw and Murray 2009). Such best-case scenarios reflect a disruptive event that impacts network operation the least. This latter case is particularly relevant to recovery since the damaged components not selected for repair should have minimal impact to network performance. Regardless of their orientation, the vulnerability assessment models referenced here are also capable of tracking impacts to network connectivity/flow since paths of movement between network origins-destinations are explicitly accounted for. Not addressed, of course, is the idea that damaged (or vulnerable) components of a network should be restored in a manner that enhances network performance the most, as such repair is not often instantaneous.

The ability to prioritize and efficiently allocate resources in support of the restoration of system performance is a critical next step in deepening our understanding of critical infrastructure vulnerability and recovery planning. In the next section, a new network restoration model is introduced to aid in the identification of efficient network recovery scenarios provided the restoration objectives of maximizing system flow and minimizing system cost. The proposed approach is structured to overcome many of the shortcomings of prior research given that: 1) no a priori assumptions on facility importance are required since actual network flow information is used to establish the importance of a repair, 2) subgraphs are readily accommodated, 3) system connectivity, flow, and cost are addressed simultaneously, and 4) restoration over all recovery periods is scheduled simultaneously, rather than incrementally.

3 Infrastructure recovery

In this paper, a multi-objective network optimization model is proposed to facilitate identification and scheduling of potential recovery scenarios following disruptions involving substantial loss of network nodes and arcs. Given limited resources for recovery efforts, the restoration of damaged components (arcs/nodes) must be prioritized across a planning horizon in order to optimize network performance. As discussed previously, an important planning goal is restoration of origin-destination (O-D) connectivity/flow (Meshkovskiy and Rokotyan 1992). Given a network G=(N,A) comprised of a set of nodes i ∈ N and arcs j ∈ A where Γn ∈ N nodes and Γl ∈ A arcs are damaged and inoperable, this would involve measuring the level of connectivity/flow enabled by scenarios involving the repair of damaged arcs and nodes over a set of planning periods t ∈ T. If o ∈ Ω indicates an origin node, d ∈ Λ indicates a destination node, and k ∈ N od is the set of paths capable of serving an O-D pair (entire set of paths denoted K), then system flow can be structured mathematically as:

$$ {\hbox{ }}\sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{\alpha_{od}}{Y_{kt}}} } } } $$
(1)

where Y kt = 1 if a path k is operable and is selected to represent connectivity between an O-D pair in time period t (Y kt = 0, otherwise), and α od indicates the flow transmitted between an O-D pair. In this context, Y kt reflects the outcome of arc and/or node repair on O-D connectivity in period t.

While system flow, or connectivity, is clearly an important consideration in network restoration, other factors like the costs associated with O-D movement are also vital to address. Thus, another objective in system restoration is cost minimization. If c kt represents the cost of traversing path k in time period t, then system cost can be represented mathematically as:

$$ \sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{c_{kt}}{Y_{kt}}} } } } $$
(2)

These two measures of system performance associated with a restoration scheme can be incorporated into a multi-objective optimization model using the following notation:

λ j :

= cost of restoring operation to arc j

λ i :

= cost of restoring operation to node i

\( {\rm H}_t^n \) :

= budget for node restoration in time t

\( {\rm H}_t^l \) :

= budget for arc restoration in time t

β t :

= weight for importance of repairs in time t

\( \Phi_k^n \) :

= set of disrupted nodes along path k

\( \Phi_k^l \) :

= set of disrupted arcs along path k

Ω odt :

= large value representing the cost of a disrupted O-D pair in time t

\( V_{jt}^l \) :

= \( \left\{ \begin{gathered} 1\,{\hbox{if}}\,{\hbox{arc}}\,j\,{\hbox{is}}\,{\hbox{operational}}\,{\hbox{in}}\,{\hbox{time}}\,t \hfill \\{\hbox{0}}\,{\hbox{otherwise}} \hfill \\\end{gathered} \right. \)

\( V_{it}^n \) :

= \( \left\{ \begin{gathered} 1\,{\hbox{if}}\,{\hbox{node}}\,i\,{\hbox{is}}\,{\hbox{operational}}\,{\hbox{in}}\,{\hbox{time}}\,t \hfill \\{\hbox{0}}\,{\hbox{otherwise}} \hfill \\\end{gathered} \right. \)

M odt :

= \( \left\{ \begin{gathered} 1\,{\hbox{if}}\,{\hbox{connectivity}}\,{\hbox{does}}\,{\hbox{not}}\,{\hbox{exist}}\,{\hbox{between}}\,{\hbox{an}}\,{\hbox{O - D}}\,{\hbox{pair}}\,{\hbox{in}}\,{\hbox{time}}\,t \hfill \\{\hbox{0}}\,{\hbox{otherwise}} \hfill \\\end{gathered} \right. \)

3.1 Networked Infrastructure Restoration Model (NIRM)

$$ Maximize\sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{\beta_t}{\alpha_{od}}{Y_{kt}}} } } } $$
(3)
$$ Minimize\sum\limits_o {\sum\limits_d {\sum\limits_t {{\Omega_{odt}}{M_{odt}} + } } } \sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{c_{kt}}{Y_{kt}}} } } } $$
(4)

Subject to:

$$ \begin{array}{*{20}{c}} {\sum\limits_{i \in {\Gamma^n}} {{\lambda_i}V_{it}^n \leqslant {\rm H}_t^n} } \hfill & {\forall t} \hfill \\\end{array} $$
(5)
$$ \begin{array}{*{20}{c}} {\sum\limits_{j \in {\Gamma^l}} {{\lambda_j}V_{jt}^l \leqslant {\rm H}_t^l} } \hfill & {\forall t} \hfill \\\end{array} $$
(6)
$$ \begin{array}{*{20}{c}} {\sum\limits_t {V_{it}^n \leqslant 1} } \hfill & {\forall i \in {\Gamma^n}} \hfill \\\end{array} $$
(7)
$$ \begin{array}{*{20}{c}} {\sum\limits_t {V_{jt}^l \leqslant 1} } \hfill & {\forall j \in {\Gamma^l}} \hfill \\\end{array} $$
(8)
$$ \begin{array}{*{20}{c}} {{Y_{kt}} - \sum\limits_{\hat t \leqslant t} {V_{i\hat t}^n} \leqslant 0} \hfill & {\forall k,i \in \Phi_k^n,t} \hfill \\\end{array} $$
(9)
$$ \begin{array}{*{20}{c}} {{Y_{kt}} - \sum\limits_{\hat t \leqslant t} {V_{j\hat t}^l \leqslant 0} } \hfill & {\forall k,j \in \Phi_k^l,t} \hfill \\\end{array} $$
(10)
$$ \begin{array}{*{20}{c}} {\sum\limits_{k \in {N_{od}}} {{Y_{kt}} + {M_{odt}} = 1} } \hfill & {\forall o,d,t} \hfill \\\end{array} $$
(11)
$$ \begin{array}{*{20}{c}} {{Y_{kt}} = \left\{ {0,1} \right\}} \hfill & {\forall k,t} \hfill \\\end{array}; \,\begin{array}{*{20}{c}} {V_{jt}^l = \left\{ {0,1} \right\}} \hfill & {\forall j \in {\Gamma^l},t} \hfill \\\end{array}; \,\begin{array}{*{20}{c}} {V_{it}^n = \left\{ {0,1} \right\}} \hfill & {\forall i \in {\Gamma^n},t} \hfill \\\end{array}; \,\begin{array}{*{20}{c}} {{M_{odt}} = \left\{ {0,1} \right\}} \hfill & {\forall o,d,t} \hfill \\\end{array} $$
(12)

Objective (3) maximizes system flow, or connectivity. Objective (4) minimizes the system cost, and is a function of continued disruption as well as path usage. Constraints (5)–(6) impose budgetary restrictions on facility restoration. Constraints (7) and (8) are structured to restrict node/arc repair to a single time period. Constraints (9)–(10) ensure that a path in period t is not available unless all component arcs and nodes are operational in period t or any preceding restoration period \( \hat t \). Constraints (11) track O-D pairs that are not connected in each time period, allowing a penalty (Ω odt ) to be assessed in objective (4) for lack of O-D connectivity. This establishes that path restoration is always beneficial to system cost as inoperability is always more costly than restoration. Constraints (11) further ensure that at most a single path is selected between an O-D pair in each time period to avoid any double counting in the model objectives. Constraints (12) are binary-integer requirements on decision variables.

Computationally there are two issues worth further discussion regarding the NIRM. First, identifying all relevant O-D paths is not trivial, so feasibility in addressing problems will depend on the ability to do so efficiently. Second, once paths have been identified, expected problem size and solution capabilities are important to address as the number of variables is largely a function of the number of paths involving damaged arcs/nodes in the network. In particular, the NIRM has \( O\left( {\left| \Omega \right| \cdot \left| \Lambda \right| \cdot \left| T \right| + \left| K \right| \cdot \left| T \right| + \left| {{\Gamma^n}} \right| + \left| {{\Gamma^l}} \right|} \right) \) decision variables and \( O\left( {\left| \Omega \right| \cdot \left| \Lambda \right| \cdot \left| T \right| + Q\left| K \right| \cdot \left| T \right| + \left| {{\Gamma^n}} \right| + \left| {{\Gamma^l}} \right| + 2\left| T \right|} \right) \) constraints, where Q represents the average number of damaged arcs/nodes in each path. The expected number of O-D paths in the network is related to the number of origins and destinations and the number of nodes and arcs. As these factors increase, the size of K and the number of constraints will also increase.

Since the NIRM has multiple objectives, it can be challenging to solve. Specifically, one must identify all or many of the tradeoff solutions for consideration in network restoration. Various methods for integrating multiple objectives and finding tradeoff solutions can be applied. The weighting method, in particular, has proven useful for finding non-dominated tradeoff solutions (Cohon 1978). For the NIRM, the weighting method involves the use of a weight w ∈ [0,1] for combining objectives (3) and (4). This can be accomplished as follows:

$$ Maximize\quad w\left( {\sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{\beta_t}{\alpha_{od}}{Y_{kt}}} } } } } \right) - \left( {1 - w} \right)\left( {\sum\limits_o {\sum\limits_d {\sum\limits_t {{\Omega_{odt}}{M_{odt}} + } } } \sum\limits_o {\sum\limits_d {\sum\limits_{k \in {N_{od}}} {\sum\limits_t {{c_{kt}}{Y_{kt}}} } } } } \right) $$
(13)

This multi-objective model can then be assessed by systematically varying the objective weight, solving the associated model, and identifying non-dominated solutions.

4 Application

The developed model is applied to support recovery planning for a telecommunications backbone network. The backbone is comprised of 46 routers (nodes) and 94 high-capacity backbones (arcs) that enable interaction between each of the 2,116 unique combinations of router pairs (Fig. 1). Flow between each of the backbone routers (α od ) was estimated as a function of city size and inter-city distance. 194,492 feasible paths of movement between network O-D pairs were identified as feasible options for O-D flow. The cost of traversing a path connecting a nodal pair (c kt ) was computed as a function of the path length as well as a weight given to each time period (i.e., β t ). It is assumed that minimizing system cost in earlier time periods is desirable, and c kt is scaled accordingly so that O-D path costs are lowest in the initial period and highest in the last period of restoration. Node repair costs are assumed to be the same for each damaged node, and similarly, arc repair costs are the same for each damaged arc.

Fig. 1
figure 1

Telecommunications network and 52 arc (\( \left| {{\Gamma^l}} \right| = 52 \)), 22 node (\( \left| {{\Gamma^n}} \right| = 22 \)) damage scenario

Full size image

The disruption to the backbone considered here involves direct damage and loss of functionality to the 52 arcs (\( \left| {{\Gamma^l}} \right| = 52 \)) and 22 nodes (\( \left| {{\Gamma^n}} \right| = 22 \)) shown in Fig. 1, simulating the potentially large-scale losses associated with a HEMP insult. In some cases, the loss of nodes indirectly renders incident arcs inoperable, although the arcs may not be physically damaged. This particular disruption scenario impacts (prevents from occurring) over 98% of system flow. System cost is also similarly degraded, due to the lack of connectivity in the network. Given that repair crews and materials necessary for restoring service to damaged components are limited in each repair period, decisions for prioritizing recovery efforts are needed.

For the telecommunications network, tradeoffs between the two model objectives are evaluated using the weighting method, allowing the weight (w) to vary between zero and one. Six repair periods are considered for arc/node repair and objective tradeoffs are assessed given a repair budget permitting the repair of a maximum of nine arcs and four nodes (\( {\rm H}_t^n = 4 \) and \( {\rm H}_t^l = 9 \)) in each period t. A commercial optimization software package, ILOG’s CPLEX 11.01, was used to obtain solutions to the NIRM. For all problem instances, solution times (quad core 2.53 GHz mobile workstation with 8 GB of RAM) averaged less than 221 s.

5 Results

In order to understand the tradeoff between the two objectives, non-dominated tradeoff solutions were identified using CPLEX for various objective weight values. These results are summarized in Fig. 2. In this figure, the x-axis depicts the system flow objective while the system cost objective is plotted on the y-axis for each of the 16 non-dominated tradeoff solutions identified. When the weight on objective (3) (x-axis) is the highest, flow restoration is given greatest priority, ensuring as much O-D flow as possible is restored in each time period. As a result, system cost is also the highest. In general, as the weight on objective (3) is decreased, O-D cost becomes more influential because costs are balanced with flow restoration over the restoration periods. As the weight on (3) approaches zero, system cost is the lowest possible, as is the level of flow restored. In an effort to highlight the differences between prioritizing system cost, system flow and tradeoffs between the two objectives, three restoration scenarios will be highlighted.

Fig. 2
figure 2

Objective tradeoffs for identified non-dominated solutions

Full size image

The first optimal restoration schedule investigated is displayed in Table 1. City (node) names are abbreviated to save space. By placing emphasis on objective (4) (w = 0.1), the model is attempting to minimize system costs. As highlighted in Table 1, 18.3% of system flow is restored for period one and a corresponding pre-disruption cost of 9.4% is realized. In repair period 1, Chicago, New York, Washington D.C (WDC) and Atlanta are restored (Fig. 3). From a network perspective, all four cities maintain a relatively significant number of local/regional connections (i.e., short-haul), greatly contributing to network efficiency (see Fig. 1). Even though the model cannot simultaneously restore all connectivity to these nodes, their abundance of lost/potential connections make them a high priority. Not surprisingly, many of the arcs selected for restoration in period one are used to better connect Chicago, NY, WDC, and Atlanta to undamaged portions of the network. Again, from a cost minimizing perspective, the short-haul segments between cities such as Chicago, Cleveland, Indianapolis, NY and WDC are relatively inexpensive to fix. In this restoration period, connectivity is also reestablished between many nodes and arcs that were not damaged during the simulated HEMP insult (e.g. Montreal, Boston, Miami). In this respect, restoration of Atlanta facilitates connectivity with undamaged network facilities in Florida, while restoration of NY reestablishes connectivity with portions of Eastern Canada.

Table 1 Optimal restoration schedule: cost minimization (w = 0.1, \( {\rm H}_t^n = 4 \), \( {\rm H}_{^t}^l = 9 \))
Full size table
Fig. 3
figure 3

Period one and two restoration: cost minimization (w=0.1)

Full size image

In restoration period one, more arcs than can actually be used are repaired given that excess budgetary resources exist. For example, the LA-Chicago and Calgary-Chicago arcs are restored although the LA and Calgary nodes have not yet been repaired. Of the three arcs that cannot be used in period one, two are immediately useful in period two restoration (LA-CHI, CAL-CHI). In addition to these legacy restorations being used in period two, four additional nodes (LA, Dallas, Calgary, and Toronto) and 9 arcs are selected for repair (Table 1 and Fig. 3). Similar to period one, six of the newly restored arcs can be used immediately, with the other three being beneficial to future repair periods (STL-SLC, LA-SLC, DAL-SLC). At this stage in the restoration effort (through period two) 53% of system flow is restored at 50.2% pre-disruption cost. The model continues to selectively repair nodes and arcs, while minimizing cost, through the remainder of the repair periods. At the end of repair period 5, 93.2% of system flow is restored and system cost is at 89.8% of the network’s pre-disrupted state. During the final repair period (period six), the San Jose and Las Vegas nodes are restored as are the 7 remaining arcs. After period six restoration has been completed, the network is operating at pre-disruption levels.

Given this solution, it is apparent that the decisions in one planning period are closely tied to others. This is not unexpected, although the degree to which these decisions are related can vary. For example, in period one, some arcs are restored for use in the current period while others are restored for use in period two. Interestingly, the SLC-POR arc is restored in period one, but cannot contribute to network performance until period three. Similarly, there are three arcs restored in period two which cannot be used until period three (Table 1). The reason for this lag in utilization is that the model permits proactive arc restoration, when sufficient budgetary resources exist, to accommodate future needs. As a result, during period one, when there is a relatively limited need for arcs (and their immediate use), NIRM restores arcs for use in subsequent repair periods where the budget is insufficient to restore all arcs that can contribute to enhanced system performance. This behavior is also evident by observing the interaction between arc restorations during periods one and two with period three activities. For example, the Salt Lake City node is directly associated with 10 arcs, but given that arc restoration is limited to 9 arcs in any time period, insufficient resources exist for restoring all of Salt Lake City’s incident arcs in period three alone. However, because the arcs between Salt Lake City, Dallas, St. Louis, Portland, and LA are restored during repair periods one and two, most arcs associated with Salt Lake City can be used in period three which is important for network performance. In essence, NIRM allows the restoration schedule to accommodate the repair of these other performance enhancing arcs during an earlier period to maximize the benefits of restoring nodes in period three. Without the analytical foresight to make the appropriate repairs in earlier stages of the restoration schedule, this type of proactive disaster mitigation would be extremely difficult. This is certainly a compelling reason to account for scheduling all repairs simultaneously versus incrementally.

Table 2 details the optimal repair strategy for w = 0.999986 with a focus on objective (3), placing an overall emphasis on restoring system flow. In this solution, the level of system flow restored is therefore greater in periods 1–5 than that attained in the cost minimizing solution. However, the system cost associated with restoration activities in periods 1–5 is also higher than in the cost minimizing recovery plan. Figure 4 illustrates flow maximizing recovery during periods one and two. In period one, the Calgary, Chicago, NY and LA nodes are selected for repair (Fig. 4). Given the emphasis on restoring flow, the inclusion of the three largest cities on the network (CHI, NY and LA) during repair period one is not surprising. The selection of Calgary seems slightly counterintuitive, until one revisits the initial disruption map (Fig. 1). While the loss of O-D flow for Calgary alone is not particularly significant, the fact that Calgary serves as an important hub for connecting portions of the Pacific Northwest (e.g., Edmonton, Vancouver, Regina) is noteworthy. Through the restoration of the Calgary node, the flow between the four Canadian cities is reestablished. The full 9 arc budget is used also used in period one with 6 arcs benefitting the system immediately, while the remaining three (Atlanta-NY, Toronto-Calgary, Dallas-WDC) are applicable to future restoration periods. Period two restoration activities involve the repair of the Washington, D.C., Atlanta, Houston, and Toronto nodes (Fig. 4). In this period, nine arcs are also restored, seven immediately contributing to network performance with the remaining two (LA-KC and Dallas-St. Louis) restored for use in subsequent periods (e.g., period four).

Table 2 Optimal restoration schedule: flow maximization (w=0.999986, \( {\rm H}_t^n = 4 \), \( {\rm H}_{^t}^l = 9 \))
Full size table
Fig. 4
figure 4

Period one and two restoration: flow maximization (w=0.999986)

Full size image

While the solutions presented in Tables 1 and 2 provide some insight on what happens when objectives (3) and (4) are considered separately, the NIRM can also be used to identify solutions that maintain some focus on both objectives simultaneously, such as those detailed in Fig. 2. Table 3 highlights one of these tradeoff solutions, w = 0.996. In this solution, more rapid increases in system flow are possible than in the cost minimizing schedule with system flow restoration slightly less than that in the flow maximizing solution. Additionally, lower system costs are possible in this solution than those found in the flow maximizing schedule. A brief comparison of Table 3 with Tables 1 and 2 reveals that in every time period similarities exist with flow maximization and cost minimization plans, while at the same time, incorporating completely different scheduling components. For instance, in period three of the tradeoff solution, one of the nodes restored corresponds with period three of the flow maximizing solution (Philadelphia) while one of the nodes (St. Louis) appears in period three of the cost minimizing solution. The other two nodes in period three of the tradeoff solution (Kansas City and Houston) appear in periods four and five of the cost minimizing solution and in periods two and four of the flow maximizing solution respectively. This example serves to illustrate the types of tradeoffs being made in the intermediate solution in that nodes significant to cost minimization and flow maximization in period three of the other two restoration plans (Seattle, Portland, Salt Lake City, Baltimore, and San Francisco) are now given less priority. Through this re-prioritization, the intermediate restoration plan can keep system costs relatively low, while accommodating substantially more flow than the cost minimizing solution.

Table 3 Optimal restoration schedule: cost/flow tradeoff (w=0.996, \( {\rm H}_t^n = 4 \), \( {\rm H}_{^t}^l = 9 \))
Full size table

As is illustrated in Figs. 3 and 4, restoration efforts oriented toward maximizing the recovery of flow and those oriented toward minimizing system cost can result in very different restoration plans. Maximizing flow (or connectivity when α od = 1) tries to ensure that demand between interacting O-D pairs is met as early as possible in the planning horizon. This objective is most similar to that addressed by Meshkovskiy and Rokotyan (1992) where they tried to reestablish connectivity between high-priority nodes in a severely damaged network. However, in the NIRM, high-priority nodes need not be identified a priori. Instead, decisions on restoration in the NIRM are based on the level of interaction that must be sustained between nodes. This is a particularly notable aspect of the proposed model, because it successfully avoids a wide array of complications that arise when ascribing nodal importance exogenously (see Grubesic et al. 2008).

That said, the process of minimizing system cost, as operationalized in this paper, encourages the restoration of low cost connectivity, facilitating efficiency between O-D pairs. As seen in Fig. 3, this encourages a tighter, more efficient network structure that emphasizes short-haul connections and connectivity over flow. Such an objective is beneficial in situations where lower costs are associated with increased capacity for facilitating interaction between nodes in close proximity. In effect, this prioritizes regional restoration. If both restoration (i.e., flow and cost) objectives are desirable, one of the other intermediate tradeoff solutions (e.g., Fig. 2) might present a good strategic compromise. For instance, the solution outlined in Table 3 might offer a desirable mix of the two objectives.

Finally, it should be noted that another possibility for addressing system flow and cost might be to consider an objective that minimizes cost weighted O-D flow. Such an objective might be a useful consideration should arc/node capacities be introduced in the model and should better estimates of O-D interaction over time become available. However, as is shown in this paper, there are tradeoffs between connectivity/flow and cost that could potentially be overlooked by combining these measures of system performance.

6 Conclusion

Many threats to network infrastructure exist with the capability of causing massive levels of damage to these systems. Given large-scale damage and associated loss of service to any networked infrastructure, it is the goal of those overseeing network operation to reestablish “normal” service as efficiently as possible. However, network recovery is often constrained by budgetary limitations and scheduling issues that make repair prioritization a necessity. The situation is further complicated by the multiplicity of recovery objectives (often competing) that need to be considered. Furthermore, even for the smallest of networks, many alternative recovery scenarios may exist and identifying and evaluating these can be challenging.

To address these issues, a multi-objective linear-integer spatial optimization model (NIRM) is proposed for informing decision-making efforts on the recovery prioritization of damaged infrastructure. In particular, two objectives are structured in the NIRM to maximize system connectivity/flow and minimize system cost over a set of planning periods. Accounting for actual levels of flow between O-D pairs is beneficial since restoration decisions are now based on the role of a damaged component to the system and not on a simple arc/node ranking mechanism. Accounting for path cost is important from an efficiency perspective both in terms of cost of connectivity and repair scheduling. Application of the NIRM shows that while these two objectives are important individually, they often identify conflicting recovery scenarios. Therefore, there are tradeoffs that must be made if both objectives are considered important to restoration efforts.

Furthermore, the results highlight the importance of scheduling restoration efforts simultaneously, rather than incrementally (i.e., period-by-period). In the case study examined, arcs are often repaired in time periods preceding the repair of associated nodes. In other words, spare resources in earlier time periods are often utilized to ensure that resource needs in future periods can be met. It should be noted however, that the model does not necessitate that all resources be utilized in the restoration process. That is, in the event that all network components can become connected at the lowest cost without repairing all damaged infrastructure, the model will not force restorations that have no impact on network performance.

Another aspect of the study worth mentioning is the broad applicability of this modeling framework. First, since the NIRM uses a path-based structure, it does not assume that connectivity initially exists between each O-D pair, a condition that is often observed in severe disasters. Second, while the analysis conducted for this paper was transcontinental in scale, the spatial scale of network restoration efforts vary widely, from the local to the global. For example, the loss of several electrical transformers during a major windstorm can impact the availability of electricity for a street block, or potentially an entire neighborhood. However, the loss of an electrical substation or a group of power generating facilities can have a much larger geographical impact—as was observed during the North American Blackout of August 2003. The point being, while these problems are dramatically different in spatial scale, an optimal strategy for network restoration is needed. To this end, the model proposed in this paper has the potential to scale rather well.

Finally, prioritizing and scheduling infrastructure restoration is a complex process that can involve a multitude of factors beyond those detailed in this paper. The NIRM presents a flexible framework within which other planning goals and constraints can be integrated. For instance, other planning considerations might include repair crew stationing and dispatching, the impact of arc/node capacity in the repair process, simultaneous improvement and repair activities, and uncertainty concerning arc/node availability and future network conditions.