ABSTRACT Title of Thesis: QUANTIFYING THE RESILIENCE OF AN URBAN TRAFFIC-ELECTRIC POWER COUPLED SYSTEM Hossein Fotouhi, Master of Science, 2016 Thesis Directed By: Professor Elise Miller-Hooks, Department of Civil and Environmental Engineering Transportation system resilience has been the subject of several recent studies. To assess the resilience of a transportation network, however, it is essential to model its interactions with and reliance on other lifelines. In this work, a bi-level, mixed-integer, stochastic program is presented for quantifying the resilience of a coupled traffic-power network under a host of potential natural or anthropogenic hazard-impact scenarios. A two-layer network representation is employed that includes details of both systems. Interdependencies between the urban traffic and electric power distribution systems are captured through linking variables and logical constraints. The modeling approach was applied on a case study developed on a portion of the signalized traffic-power distribution system in southern Minneapolis. The results of the case study show the importance of explicitly considering interdependencies between critical infrastructures in transportation resilience estimation. The results also provide insights on lifeline performance from an alternative power perspective. QUANTIFYING THE RESILIENCE OF AN URBAN TRAFFIC-ELECTRIC POWER COUPLED SYSTEM by Hossein Fotouhi Thesis submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Master of Science 2016 Advisory Committee: Dr. Elise Miller-Hooks, Chair Dr. Paul M. Schonfeld Dr. Lewis E. Link © Copyright by Hossein Fotouhi 2016 ii Acknowledgements I would like to thank my advisor Professor Elise Miller-Hooks for all her help and support during my studies at University of Maryland. iii Table of Contents Acknowledgements ....................................................................................................... ii Table of Contents ......................................................................................................... iii List of Tables ............................................................................................................... iv List of Figures ............................................................................................................... v Chapter 1: Introduction ................................................................................................. 1 Chapter 2: Interdependencies and the Literature .......................................................... 5 Chapter 3: Problem Formulation ................................................................................ 15 3.1 Problem Formulation ........................................................................................ 20 3.1.1 Post-event power distribution - traffic signal status .................................. 21 3.1.2 Budget Limitation ...................................................................................... 23 3.1.3 Traffic Flow and Link Capacities .............................................................. 24 3.1.4 KKT Conditions ......................................................................................... 24 3.1.5 Link Travel Times...................................................................................... 25 3.1.6 Link Status ................................................................................................. 26 3.1.7 Repair Operations Limitations ................................................................... 27 3.2 Linear approximation ........................................................................................ 28 3.2.1 Linearizing the objective function ............................................................. 28 3.2.2 Linearizing the BPR function .................................................................... 28 3.2.3 Linearizing complementarity constraints ................................................... 31 3.2.4 Other constraints ........................................................................................ 32 Chapter 4: Illustrative Example .................................................................................. 34 4.1 Case study ......................................................................................................... 34 4.2 Experimental Design ......................................................................................... 39 4.3 Analysis of Run Results .................................................................................... 40 Chapter 5: Conclusions, Limitations and Extensions ................................................ 49 Appendix A ................................................................................................................. 56 Bibliography ............................................................................................................... 57 iv List of Tables Table 1- Literature review summary ........................................................................... 12 Table 2- Link Attributes.............................................................................................. 36 Table 3- O-D pair details ............................................................................................ 36 Table 4- Total post-disaster unmet power demand by scenario and budget level ...... 41 Table 5- Total post-disaster unmet power demand by scenario with budget available only to transportation network .................................................................................... 43 Table 6- Total post-disaster unmet power demand by scenario and budget level (in $1,000s) with budget available only to power network .............................................. 43 v List of Figures Figure 1-Interdependencies between transportation and other critical lifelines ........... 6 Figure 2- Simplified electric power system ................................................................ 34 Figure 3- Case Study Area (South Minneapolis), map created using ESRI’s ArcGIS® 10.3.............................................................................................................................. 35 Figure 4- Roadway network with link IDs ................................................................. 35 Figure 5- Substations Service Areas (Zima, 2009) ..................................................... 38 Figure 6- Simplified Transportation-Power Coupled Network .................................. 38 Figure 7- 4 scenarios (damaged components in dashed lines) .................................... 39 Figure 8- Resilience by budget level .......................................................................... 41 Figure 9- Resilience by strategy: distributing budget between networks ................... 43 Figure 10- Resilience level under restricted repair opportunities ............................... 45 Figure 11- The value of considering stochasticity and perfect information (Budget=$40,000) ....................................................................................................... 47 1 Chapter 1: Introduction Transportation networks are critical lifelines for a community, essential to the functioning of society and the viability of its economy. Similar to other civil infrastructure systems (e.g. electric power, telecommunications and water supply), transportation systems are vulnerable to a host of hazards and other less extreme causes of disruption. Thus, having a resilient transportation infrastructure system, i.e. one that has both the innate capacity and adaptive capacity to withstand the impact of one of various types of hazard events, is critical. In a disaster event, a well-operating transportation system is also crucial to search and rescue efforts, accessibility by emergency personnel, evacuation and sheltering, distribution of essential supplies, and the ability to respond quickly to acute medical needs. After a disaster, a functioning transportation network allows a community to repair damaged infrastructures and recover economically. According to the Department of Homeland Security (DHS), resilience is defined as “the ability to prepare for and adapt to changing conditions and withstand and recover rapidly from disruptions.” They consider that disruptions may be generated deliberately, accidental or from natural occurrences. Transportation system resilience and related measures of risk, vulnerability, reliability and others have been studied in several works. These works have focused on a range of transportation modes, such as cargo, roadway, and aviation. A comprehensive review of approximately 200 related articles is given by Faturechi and Miller-Hooks (2014). Across the board, these works 2 consider the transportation system in isolation, overlooking its dependencies on, or interconnections with, other critical infrastructures. In fact, continued operation of these systems has come to rely on other infrastructure systems, especially power and telecommunications. Even co-location with, for example, water supply and sewage systems creates interconnections. These interactions can cause cascading failures that propagate from one system to another and back. Studying the resilience of a transportation system in isolation may create erroneous conclusions. This is because resilience estimates taken in isolation likely will not account for damage and/or repairs taken to the other interacting systems under a damage scenario. To address this, one might anticipate the impacts of the damage event and predict a likely repair schedule. However, it may be necessary in developing the repair schedule for the second infrastructure to consider damage and repair schedules designed for the transportation system, since moving equipment and personnel over a geographic area may be required. Additionally, adaptive actions taken in the immediate aftermath of a disruption event affecting the transport system would need to be identified with limited knowledge about other supporting lifelines. Such adaptive actions are a crucial component of resilience estimation. Thus, to assess the resilience of a transportation network, it is essential to model its interactions with these other lifelines. In this thesis, a mathematical modeling approach is proposed for computing and maximizing the resilience of a coupled transportation-power network. Specifically, a bi-level, two-stage, stochastic, mixed-integer, nonlinear program is developed with the 3 goal of maximizing resilience in terms of performance of the transportation system. Interdependencies and other interactions are modeled through linking variables and logical constraints. The model explicitly recognizes the inherent stochasticities in the impact of future hazard events from possible multiple hazard types. This bi-level framework with stochastic program at the upper level can be viewed as an extension of an earlier multi-hazard resilience computation methodology described in (Faturechi and Miller-Hooks, 2014, for a traffic network) to multiple interdependent networks. The upper level seeks an optimal allocation of limited mitigation, preparedness and response resources to obtain an efficient resource allocation plan across systems and estimate maximum achievable resilience level given traffic flows through network arcs. The upper level is formulated as a two-stage, stochastic, mixed-integer, nonlinear program with an objective of minimizing total system travel time. Travel times are estimated in the lower level assuming a traffic equilibrium will be achieved under given resilience enhancing actions (i.e., mitigation/preparedness and recovery decisions) from the upper level. Maximum coupled-system resilience is obtained when a Stackelberg equilibrium is reached between the upper- and lower-level problems (Gibbons, 1992). The two-stage stochastic programming framework adopted herein captures differences in information availability between pre-event and post-event decision- making. In the first stage, decisions on preparedness and mitigation actions are chosen, while in the second stage, recourse actions are taken for the realized hazard event using information on concomitant damage impact over the coupled system. The components 4 of this coupled network that are vulnerable to damage include traffic signal and roadway links (traffic network), and also substations, and transmission lines (power network). Recourse actions, such as repairing a downed power line, can be applied across the networks; however, their availability may necessitate the need for an open path along which a repair crew can travel to reach the affected equipment. Hazard type and impact uncertainty is modeled through the generation of multiple disaster event impact scenarios that are designed to reflect different levels of damage to the various elements of the coupled system. Next (Chapter 2), models that consider interdependence between a transportation system and other critical infrastructures are synthesized, and a review of general approaches for modeling interdependent systems is provided. This is followed by the mathematical model proposed herein for transportation resilience computation and maximization in a coupled traffic-power system (Chapter 3). Using previously developed techniques and established theories, the bi-level program is reduced to an equivalent single-level program (also in Chapter 3). The proposed method was applied to a case study involving a portion of the signalized traffic-power distribution system in southern Minneapolis (Chapter 4). Concluding remarks are given in Chapter 5. 5 Chapter 2: Interdependencies and the Literature Interactions between transportation and other infrastructure systems can be one-way (dependencies) or two-way (interdependency). Rinaldi et al. (2001) categorized interdependencies between critical lifelines into four general types: physical, cyber, geographic, and logical. Consider the following examples in the context of transportation applications. The safe and uninterrupted operation of a railway system relies on continuous communications between trains and the control room, creating a cyber interdependency. Moreover, operation of both the railway and communications networks depend on stable electric power, and the viability of the power network depends on the communications network, producing physical, direct and indirect interdependencies. In the context of a roadway network, a water-main break arising below the surface of a roadway may cause traffic congestion, further prolonging the period before which repair teams can reach affected areas. This produces greater and more widespread congestion and, thus, geographic interdependency. Logical interdependencies in the context of transportation systems may arise, for example, where substitutable travel modes exist. Some interactions arise from the disaster circumstance; while other interactions exist during normal operations due to physical connections or other dependencies. These interactions generally arise between transportation and other critical lifelines, including not only power, communications, and water/waste water, but also supply chains, emergency-repair services, and health care, among others. Figure 1 illustrates these and other interdependencies between transportation systems and other critical lifelines. 6 Figure 1-Interdependencies between transportation and other critical lifelines While discussion of resilience in the literature has increased tremendously in recent years, few works have focused on specifics of the interactions between a transportation system and other lifelines. The succeeding paragraphs describe the specific causes of interconnectivity with power, telecommunications, water supply or wastewater networks, and seek to uncover issues that may arise due to such interactions. Power is vital for ensuring continuity of operations of many transportation systems. Several works consider the dependence of the transportation system, e.g. 7 railroad networks (Zhang et al., 2014, Lee et al., 2007, Santos-Reyes et al., 2015), airports (Procyk and Dhariwal, 2010), and signalized traffic intersections (Bigger et al., 2009, Procyk and Dhariwa, 2010, Kajitani and Sagai, 2009) on electric power. On the other hand, power systems can be affected by disturbances in transportation systems. Consider, for example, interruptions in power in the context of a railroad system. Delays in delivery of coal needed for electric-power generation at power plants will arise due to power loss, causing failure to railroad control and highway-railroad crossing signals. These delays affect the restoration of the power network, which is required for reducing travel delays. Such interdependencies between roadway and power networks were noted in several events that arose during the 2004 hurricane season in Florida, and are studied in (Bigger et al., 2009). Communication also plays a very important role in operations of many transportation systems as is discussed in several works. Specifically, railroad and air transport systems rely heavily on functioning communication systems (Bigger et al., 2009, Procyk and Dhariwal, 2010). Moreover, coordinating emergency response and post-event repair operations also requires communication between units (Bigger et al., 2009, Procyk and Dhariwal, 2010). The role of backup systems, such as radios (Procyk and Dhariwal, 2009), in alleviating communication outages is discussed in the context of structural closures and contraflow operations. Water and wastewater systems also depend on the transportation system. This dependence arises from a need for supplies of chemicals for water/wastewater treatment that are typically carried by trucks (Bigger et al., 2009, Procyk and Dhariwal, 8 2010). On the other hand, a water main break can lead to flooding, which may cause roadway closures (Procyk and Dhariwal, 2010), and the use of roadways is required for repairing the water pipelines. A comprehensive review of over 200 articles on the general modeling of interconnected critical infrastructure systems is given in (Ouyang, 2014). This work classifies the various approaches as: empirical, agent-based, system dynamic, economic theory, network and others. In the context of transportation related interdependency studies, empirical methodologies, i.e. using existing data from previous events or expert judgment, were employed in (Bigger et al., 2009; Procyk and Dhariwal, 2010; Huang et al., 2014). By example, Bigger et al. (2009) gather data from interviews with owners and operators of major critical lifelines. Their main aim was to reveal key interdependencies among energy, communication, water/wastewater, and transportation during the 2004 hurricane season in Central Florida. A disadvantage of such empirical models is their strong dependence on subjective opinion and accurate reporting. Alternative quantitative approaches to studying interdependencies involving transportation systems have been proposed. These include: simulation-, graph theoretic-, mathematical modeling-, and network flow-based methodologies. Simulation-based methods were employed in (Zhang et al., 2014; Johansson and Hassel, 2010; Cui et al., 2014; Arcidiacono et al., 2012) for assessing the impact of interactions between transportation and other systems. Zhang et al. (2014) employed a graph-theoretic approach to assess dependencies between the rail network and power 9 and communication systems. They evaluated the Shanghai urban rail transit network’s vulnerability using a concept of dependent intensity within a framework of master and slave networks. Functionality loss of this rail system was evaluated for three different types of failure in each master network (communication and power) for a range of dependent intensities. Simulation runs were conducted to determine the critical nodes of power and communication networks based on rail functionality loss. Johansson and Hassel (2010) evaluated disruptions on the vulnerability of interconnected infrastructure networks through the simulation of node and edge removal. Connections are modeled through dependency links between infrastructure network representations. A case study of a hypothetical railway system modeled on a real railway network in Sweden was conducted. This railway system depends on: electrical in-feed, auxiliary power, telecommunication, and traction power systems. Critical system components and critical geographic locations were identified based on loss of origin-destination connectivity in the railway system. Their modeling approach captures the temporal aspects of repair time and buffer capacity. Cui et al. (2014) studied the impacts of hurricanes on transportation and health care systems. They conducted simulation runs to estimate the effect of different strategies for recovering roadways and regaining access to hospitals. Arcidiacono et al. (2012) proposed a methodology to measure the resilience index for transportation system during a disaster considering its interdependencies with building systems. In this paper, the functionality of transportation system is defined as post-disaster capacities over pre-disaster capacities for different transportation systems such as roadway networks, port, and airports. The 10 proposed method is implemented in a software and has been applied to a case study of San Francisco Bay area. Zhang and Peeta (2011) employed a multi-layer infrastructure network framework to study interdependencies between infrastructure systems. In such a framework each infrastructure is modeled as a layer containing multiple geographical regions, where a transport agent associated with each infrastructure is responsible for moving commodities produced within the system between different regions. Interactions between infrastructures are captured through a market-based economic approach employing computable general equilibrium (CGE) theory. Substitution relationships between different infrastructures with benefits for producers and households are modeled for the case of a supply reduction in one commodity under an interruption. Another multi-layer representation and mathematical modeling perspective in taken in (Gong et al., 2014) in studying the optimal restoration strategy for supply chains using a multi-objective optimization approach. The supply chain, power system and telecommunication networks are each modeled as a layer and interdependencies between them are also represented through logical constraints. In their model, the transportation network is embedded within the supply chain layer. Cavdaroglu et al. (2013) proposed a mixed integer formulation for integrating restoration and scheduling plans to restore services to interrupted interdependent systems (described generically) in the aftermath of a disruption. Restoration decisions are taken and are assigned to an available work group. They tested their model on a case study involving power and telecommunication infrastructures within Manhattan. 11 A multicommodity network flow model of the interconnected power, telecommunication, and subway networks is proposed in (Lee et al., 2007). Each of these networks is modeled as an individual system using a deterministic mathematical modeling approach wherein system interactions are represented through constraints. Five types of dependencies were studied: input (one system feeds the other), mutual (interdependence), shared (need for same resource), exclusive OR, and co-located. The approach was applied on a case study involving the subway system in Lower Manhattan under a single, hypothetical disruption scenario. The aim of the model is to propose an optimal restoration plan. A plan for the post-event placement of power shunts was identified for bringing services temporarily back on line under the given scenario. One can categorize these examples of interdependencies between critical infrastructures as operational or infrastructural failure interdependencies. Another type of interdependency between lifelines occurs when restoration actions in one system affect the restoration efforts in another (Sharkey, Nurre, Nguyen, Chow, Mitchell, and Wallace, 2015). For example, debris that is left post-event may block roadway links near a power substation; thus, preventing repairs to that substation. Restoration of power depends on the restoration of the roadway links. Sharkey, Nurre, et al. (2015) classified the restoration interdependencies into two broad categories: time-based (traditional precedence, effectiveness precedence, option precedence, and time- sensitive options) and resource-based (competition for resources). The first category concerns post-event repair scheduling and the effects of timing repairs on operations of other infrastructures. 12 Table 1- Literature review summary Type of study Transportation Mode Roadway Rail Aviation Ports & Waterways Cr itic al Inf ras tru ctu re Electric Power Qual* Bigger et al. (2009), Procyk and Dhariwal (2010), Sharkey, Nurre, et al. (2015) Procyk and Dhariwal (2010), Sharkey, Nurre, et al. (2015)  Procyk and Dhariwa l (2010)  Quan** Huang et al. (2014) Zhang et al. (2014), Lee et al (2007), Huang et al. (2014), Johansson and Hassel (2010)  Huang et al. (2014) Huang et al. (2014) Communica tion Qual Bigger et al. (2009), Procyk and Dhariwal (2010) Procyk and Dhariwal (2010)   Quan Huang et al. (2014), Gong et al. (2014) Zhang et al. (2014), Lee et al (2007), Huang et al. (2014), Johansson and Hassel (2010)  Huang et al. (2014) Huang et al. (2014) Water/Wast ewater Qual Procyk and Dhariwal (2010), Bigger et al. (2009)    Quan Huang et al. (2014) Huang et al. (2014)  Huang et al. (2014) Huang et al. (2014) Natural Gas Qual Sharkey, Nurre, et al. (2015)    Quan Huang et al. (2014) Huang et al. (2014)  Huang et al. (2014) Huang et al. (2014) Supply Chain & Fuel Supply Qual Procyk and Dhariwal (2010)    Sharkey, Nurre, et al. (2015) Quan Huang et al. (2014), Gong et al. (2014) Huang et al. (2014)  Huang et al. Huang et al. (2014) 13 (2014) Repair & Emergency Services Qual Bigger et al. (2009), Sharkey, Nurre, et al. (2015)    Quan Arcidiacono et al. (2012), Sharkey, Cavdaroglu, et al. (2015)    Health Care Qual Bigger et al. (2009)    Quan Cui et al. (2014)    *Qualitative approaches **Quantitative approaches Finally, Sharkey, Cavdaroglu, Nguyen, Holman, Mitchell, and Wallace (2015) proposed mathematical models to study the potential for centralized and decentralized decision making to impact system recovery. In the former case, all systems are considered simultaneously with one governing decision-maker who seeks optimal multi-system performance using a joint objective function; while in the latter case, decisions are taken unilaterally for each network. Their models were employed on two case studies to study the role of information sharing in system restoration efficiency with a focus on power, telecommunication, transportation, and water/wastewater infrastructures. Transportation was considered only in terms of emergency response generated from police and fire stations to population centers. Interdependencies associated with restoration activities are captured through logical constraints in the models. Average percentage of disrupted service restored across the infrastructures serves as a performance metric. Table 1 synthesizes the inclusion of transportation systems in critical lifeline interdependency modeling. Most of the papers that have studied transportation-related 14 interdependencies have only established the types of interdependencies between transportation systems and other critical lifelines and provided examples for each type. A small subset of these works have proposed modeling approaches to study these interdependencies. However, most only conduct a vulnerability analysis to identify weaknesses due to interdependencies. This review of the literature revealed six studies on transportation system resilience quantification given its reliance on and interdependencies with other critical lifelines. While these works provide methods that consider interconnections between some infrastructures and transportation systems, none considers increasing resilience of such an interconnected system through taking preparedness/mitigative actions in an uncertain environment. This work takes a step toward filling this gap. Specifically, it incorporates both the network’s inherent coping capacity and post-event adaptability (two key components of resilience) in resilience measurement and maximization for the coupled signalized roadway-power network. The resilience measure is based on total travel time assuming drivers will seek alternative, shorter paths when intersection delays or roadway link blockages arise, thus accounting for the impact of power outages and their remediation at the intersections. Interdependencies arising from the need for transport access for repair crews in the power distribution network are included. Moreover, the approach is multi-hazard and accounts for the uncertainties inherent in future hazard events. 15 Chapter 3: Problem Formulation The problem of computing the maximum resilience level of the coupled traffic-power system is formulated in this chapter using concepts of a bi-level formulation. A single- level equivalent problem is presented; its equivalency is discussed. Before proceeding to the formulation, nomenclature is defined. The notation assumes that only one mitigation, one preparation and one response action can be taken on any node or link element. The latter need not be restrictive as sets of actions can be bundled. The term signal refers to the traffic controller equipment, including the set of traffic lights controlling the movement of vehicles through a single intersection. If power is lost to the intersection or any portion of this equipment is damaged, the entire intersection control system is assumed to go down. Parameters ݉௘௦௨௕ cost of implementing preparedness action on substation ݁ ∈ ܧ ݉௧௦௜௚ cost of implementing preparedness action on signal ݐ ∈ܶ ݉௩௟௜௡௞ cost of implementing preparedness action on link ݒ ∈ ܸ ݊௘௦௨௕ cost of implementing recovery activity on substation ݁ ∈ܧ ݊௧௦௜௚ cost of implementing recovery activity at signal ݐ ∈ ܶ ݊௩௟௜௡௞ cost of repairing link ݒ ∈ ܸ ݊௟௧௥௔௡௦ cost of repairing transmission line ݈ ∈ ܮ 16 ݊௧௣௢௟௜௖௘ cost of implementing police enforcement at signal ݐ ∈ ܶ ݊௘௣_௦௨௕ cost of implementing recovery activity on substation ݁ ∈ܧ if preparedness action is taken on the substation ݊௧௣_௦௜௚ cost of implementing recovery activity at signal ݐ ∈ ܶ if preparedness action is taken on the signal ݊௩௣_௟௜௡௞ cost of repairing link ݒ ∈ ܸ if preparedness action is taken on the link ߣ௦௨௕ preparedness-recovery activity relationship (=1 if recovery activity taken on substations is affected by preparedness action taken on substations and =0 otherwise) ߣ௦௜௚ preparedness-recovery activity relationship (=1 if recovery activity taken on signal is affected by preparedness action taken on signal and =0 otherwise) ߣ௟௜௡௞ preparedness-recovery activity relationship (=1 if repair of link is affected by preparedness action taken on link and =0 otherwise) ܤ available budget ܥ௔ capacity of link ܽ ∈ ܣ ∆ܥ௩ capacity reduction in link ݒ ∈ ܸ if no preparedness or recovery activity is taken on link ݒ ∆ܥ௩௣ capacity reduction in link ݒ ∈ ܸ if preparedness action is taken on link ݒ ݍ௪ demand for O-D (Origin-Destination) pair ݓܹ߳ ݈݀݁ܽݕ௔ௗ௢_௡௢௧௛௜௡௚ travel delay along link ܽ ∈ ܣ if outage at signal at terminating end of link ܽ ݈݀݁ܽݕ௔௣௢௟௜௖௘ travel delay along link ܽ ∈ ܣ if outage at signal at terminating end of link ܽ with police reinforcement ߜ௔,௞௪ path-arc incidence (=1 if path ݇ ∈ ܭ௪ uses link ܽ ∈ ܣ for O-D pair ݓ ∈ ܹ and =0 otherwise) 17 ∆௔,௞௡ path-arc incidence (=1 if path ݇ ∈ ܭ௡ uses link ܽ ∈ ܣ for reaching node ݊ ∈ ܰ and =0 otherwise) ௔ܰ,௧ link-signal incidence (=1 if signal ݐ ∈ ܶ is at terminating end of link ܽ ∈ ܣ and =0 otherwise) ܯ௘,௙ substation-feeder incidence (=1 if substation ݁ ∈ ܧ provides electricity for feeder ݂ ∈ ܨ and =0 otherwise) ܪ௟,௨ transmission line-substation-feeder-signal incidence defined for each pair of transmission line ݈ ∈ ܮ and ݑ ∈ ܷ, where ݑ can be either a substation, ݁, feeder, ݂, or signal, ݐ (=1 if transmission line ݈ starts from either substation ݁ ∈ ܧ ⊆ ܷ or feeder ݂ ∈ ܨ ⊆ ܷ, -1 if it ends at either feeder ݂ ∈ ܨ ⊆ ܷ or signal ݐ ∈ ܶ ⊆ ܷ, and =0 otherwise) ܳ௙,௧ feeder-signal incidence (=1 if feeder ݂ ∈ ܨ provides electricity for signal ݐ ∈ ܶ and =0 otherwise) ܩ௘,௡ substation-intersection incidence (=1 if substation ݁ ∈ ܧ is located at node ݊ ∈ ܰ and =0 otherwise) ௟ܱ,௡ transmission line-intersection incidence (=1 if transmission line ݈ ∈ ܮ originates from or terminates at node ݊ ∈ ܰ and =0 otherwise) ܫ௧,௡ signal-intersection incidence (=1 if signal ݐ ∈ ܶ is located at node ݊ ∈ ܰ and =0 otherwise) ݐ௔଴ free flow travel time of link ܽ ∈ ܣ ݏݑܾ௘(ݏ) state of substation ݁ ∈ ܧ, indicating whether substation can provide feeders with electricity under scenario ݏ ∈ ܵ (=1 if it can provide electricity and =0 otherwise) ݏ݅݃௧(ݏ) state of signal ݐ ∈ ܶ, indicating whether signal is damaged under scenario ݏ ∈ ܵ (=1 if it is not damaged and =0 otherwise) ݉ܽ݅݊_ݐݎܽ݊ݏ௟(ݏ) state of main transmission line ݈ ∈ ܮଵ, indicating whether main transmission line is damaged under scenario ݏ ∈ ܵ (=1 if it is not damaged and =0 18 otherwise) ݏ݁ܿ݋݊݀ܽݎݕ_ݐݎܽ݊ݏ௟(ݏ) state of secondary transmission line ݈ ∈ ܮଶ, indicating whether secondary transmission line is damaged under scenario ݏ ∈ ܵ (=1 if it is not damaged and =0 otherwise) ݈݅݊݇௩(ݏ) state of link ݒ ∈ ܸ,indicating whether link is damaged under scenario ݏ ∈ ܵ (=1 if it is not damaged and =0 otherwise) Auxiliary Variables ܥ௔௡௘௪(ݏ) new (updated) capacity of link ܽ ∈ ܣ given resilience enhancing actions taken on link ܽ under scenario ݏ ∈ ܵ ݏ݅݃௧௙௜௡௔௟(ݏ) indicates whether signal ݐ ∈ ܶ is working under scenario ݏ ∈ ܵ (=1 if it is working and =0 otherwise) ݈݅݊݇௩௙௜௡௔௟(ݏ) indicates whether link ݒ ∈ ܸ is working under scenario ݏ ∈ ܵ (=1 if it is working and =0 otherwise) ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) indicates whether feeder ݂ ∈ ܨ receives power from its upstream substation under scenario ݏ ∈ ܵ (=1 if it receives power and =0 otherwise) ݕ௙௠௔௜௡_௧௥௔௡௦(ݏ) indicates whether the main transmission line in feeder ݂ ∈ ܨ is operational under scenario ݏ ∈ ܵ (=1 if it is operational and =0 otherwise) ݕ௙௘௟௘௖_௣௢௪௘௥_௜௡_௙௘௘ௗ௘௥(ݏ) indicates whether feeder ݂ ∈ ܨ has power along its main transmission lines under scenario ݏ ∈ ܵ (=1 if it has power and =0 otherwise) ݕ௧௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ) indicates the state of a secondary transmission line that connects feeder ݂ ∈ ܨ to signal ݐ ∈ ܶ under scenario ݏ ∈ ܵ (=1 if it is operational and =0 otherwise) ݕ௧௘௟௘௖_௣௢௪௘௥_௔௧_௦௜௚௡௔௟(ݏ) indicates whether signal ݐ ∈ ܶ has power under scenario ݏ ∈ ܵ (=1 if it has power and =0 otherwise) ݌ܽݐℎ௞௡(ݏ) binary variable that indicates whether all links along path ݇ ∈ ܭ௡ from repair crew depot to node ݊ ∈ ܰ are working (i.e. path is open) under scenario ݏ ∈ ܵ (=1 if 19 all links along path ݇ ∈ ܭ௡ are open and =0 otherwise) ݐ௔(ݏ) post-disaster travel time along link ܽ ∈ ܣ under scenario ݏ ∈ ܵ ܼ post-disaster total travel time (expected value over all scenarios ݏ ∈ ܵ) ݔ௔(ݏ) post-disaster traffic flow on link ܽ ∈ ܣ under scenario ݏ ∈ ܵ ߨ௪(ݏ) post-disaster minimum travel time for O-D pair ݓ ∈ ܹ under scenario ݏ ∈ ܵ, given all resilience-enhancing actions that were taken ݌௞௪(ݏ) travel time of path ݇ ∈ ܭ௪ for O-D pair ݓ ∈ ܹ under scenario ݏ ∈ ܵ ݎ௞௪(ݏ) traffic flow on path ݇ ∈ ܭ௪ for O-D pair ݓ ∈ ܹ under scenario ݏ ∈ ܵ Resilience enhancing decision variables ߚ௘௦௨௕ indicates whether a preparedness action is taken on substation ݁ ∈ ܧ (=1 if preparedness action is taken on substation ݁ and =0 otherwise) ߚ௧௦௜௚ indicates whether a preparedness action is taken at signal ݐ ∈ ܶ (=1 if preparedness action is taken on signal ݐ and =0 otherwise) ߚ௩௟௜௡௞ indicates whether a preparedness action is taken on link ݒ ∈ ܸ (=1 if preparedness action is taken on link ܽ and =0 otherwise) ߛ௘௦௨௕(ݏ) indicates whether a recovery activity is taken on substation ݁ ∈ ܧ (=1 if recovery activity is taken on substation ݁ and =0 otherwise) ߛ௧௦௜௚(ݏ) indicates whether a recovery activity is taken at signal ݐ ∈ ܶ (=1 if recovery activity is taken at signal ݐ and =0 otherwise) 20 ߛ௩௟௜௡௞(ݏ) indicates whether a recovery activity is taken on link ݒ ∈ ܸ (=1 if recovery activity is taken on link ݐ and =0 otherwise) ߛ௟௠௔௜௡_௧௥௔௡௦(ݏ) indicates whether a recovery activity is taken on main transmission line ݈ ∈ ܮଵ (=1 if recovery activity is taken on main transmission line ݈ and =0 otherwise) ߛ௟௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ) indicates whether a recovery activity is taken on secondary transmission line ݈ ∈ ܮଶ (=1 if recovery activity is taken on secondary transmission line ݈ and =0 otherwise) ߛ௧௣௢௟௜௖௘(ݏ) indicates whether police are assigned to regulate the intersection movements for intersection associated with signal ݐ ∈ ܶ (=1 if recovery activity is taken and =0 otherwise) 3.1 Problem Formulation With the traffic network as the focus, the objective of maximizing resilience is given in terms of total travel time. Specifically, resilience is defined as the ratio of pre-event total travel time (defined in terms of vehicular travel time under pristine conditions) to post-event total travel time (defined in terms of mean vehicular travel time taken over all possible hazard scenarios): Resilience = pre − event total travel timepost − event total travel time Total travel times are weighted by demand for each O-D pair. Since the numerator is a constant, it can be omitted from the objective function (1). The objective is, thus, rewritten in terms of minimizing the expected total system travel time for all users summed over all scenarios, weighted by scenario probabilities. 21 ܯ݅݊ ܼ = ܧ௦ ൥෍ ݔ௔(ݏ)ݐ௔(ݏ) ௔∈஺ ൩ (1) The objective is subject to constraints associated with: the status of both power distribution and traffic signal systems, budget, traffic link flows, roadway link capacities, KKT (Karush-Kuhn-Tucker) conditions, roadway link repair needs, and repair operation limitations due to interdependencies affecting restoration. The remainder of this section is dedicated to the description and formulation of these constraints. 3.1.1 Post-event power distribution - traffic signal status Auxiliary constraints (2)-(8) determine whether the traffic signals will be operative post-event given direct damage, damage to the power distribution components that support them, and preparedness or recovery actions taken to mitigate the impact of such damage should it occur. Such actions include, for example, hardening roadway links, placing generators at substations and providing alternative energy (such as solar) for traffic signal controllers. Backup power generators generate less power than a typical substation. Consequently, a generator that serves as a temporary replacement for a substation will support only a subset of its associated feeders. By constraints (2), a feeder ݂߳ܨଵ has power under scenario s if one or more of the following conditions hold: substation e that feeds f is undamaged under scenario s (first term on the right-hand side), a preparedness action is taken to provide backup power generation at substation e in case of damage, i.e. ߚ௘௦௨௕ = 1 (second right-hand side term), or substation e is repaired post- 22 event, i.e. ߛ௘௦௨௕(ݏ) = 1. If any of these conditions hold, then ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) = 1 and feeder f can receive power from its substation. For f not in ܨଵ (constraints (3)), f is operational only if the substation is undamaged or repaired. 1 − ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) = ൭1 − ෍ ܯ௘,௙ݏݑܾ௘(ݏ) ௘∈ா ൱ ൭1 − ෍ ܯ௘,௙ߚ௘௦௨௕ ௘∈ா ൱ ൭1 − ෍ ܯ௘,௙ߛ௘௦௨௕(ݏ) ௘∈ா ൱ , ∀݂ ∈ ܨଵ, ݏ ∈ ܵ, (2) 1 − ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) = ൭1 − ෍ ܯ௘,௙ݏݑܾ௘(ݏ) ௘∈ா ൱ ൭1 − ෍ ܯ௘,௙ߛ௘௦௨௕(ݏ) ௘∈ா ൱, ∀݂ ∈ ܨ − ܨଵ, ݏ ∈ ܵ. (3) A similarly structured set of constraints (4) can be formulated to determine the state of the main transmission line under scenario s that emanates from a substation. If the main transmission line is undamaged or repaired, and the feeder can obtain power from its substation (i.e. ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) = 1), then it is able to distribute power, i.e. ݕ௙௘௟௘௖_௣௢௪௘௥_௜௡_௙௘௘ௗ௘௥(ݏ) = 1 (constraints (5)). 1 − ݕ௙௠௔௜௡_௧௥௔௡௦(ݏ) = ቌ1 − ෍ ቀ−ܪ௟,௙ ∙ ݉ܽ݅݊_ݐݎܽ݊ݏ௟(ݏ)ቁ ௟∈௅భ ቍ ቌ1 − ෍ ቀ−ܪ௟,௙ߛ௟௠௔௜௡_௧௥௔௡௦(ݏ)ቁ ௟∈௅భ ቍ, ∀݂ ∈ ܨ, ݏ ∈ ܵ. (4) ݕ௙௘௟௘௖_௣௢௪௘௥_௜௡_௙௘௘ௗ௘௥(ݏ) = ቀݕ௙௘௟௘௖_௣௢௪௘௥(ݏ)ቁ ቀݕ௙௠௔௜௡_௧௥௔௡௦(ݏ)ቁ, ∀݂ ∈ ܨ, ݏ ∈ ܵ. (5) Next, constraints are required to ensure that end users receive power only if transmission lines between the main transmission line and the end users are operational (constraints (6)). Thus, for signal t, ݕ௧௘௟௘௖_௣௢௪௘௥_௔௧_௦௜௚௡௔௟(ݏ) = 1, inferring that 23 everything is in place for power at the signal (constraints (7)). 1 − ݕ௧௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ) = ቌ1 − ෍ ቀ−ܪ௟,௧ ∙ ݏ݁ܿ݋݊݀ܽݎݕ_ݐݎܽ݊ݏ௟(ݏ)ቁ ௟∈௅మ ቍ ቌ1 − ෍ ቀ−ܪ௟,௧ߛ௟௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ)ቁ ௟∈௅మ ቍ , ∀ݐ ∈ ܶ, ݏ ∈ ܵ. (6) ݕ௧௘௟௘௖_௣௢௪௘௥_௔௧_௦௜௚௡௔௟(ݏ) = ൮෍ ܳ௙,௧ ௙∈ி ݕ௙௘௟௘௖_௣௢௪௘௥_௜௡_௙௘௘ௗ௘௥(ݏ)൲ ቀݕ௧௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ)ቁ, ∀ݐ ∈ ܶ, ݏ ∈ ܵ. (7) With power at signal t, the signal is operational under scenario s (ݏ݅݃௧௙௜௡௔௟(ݏ) = 1) if the signal is undamaged or repaired. ݏ݅݃௧௙௜௡௔௟(ݏ) = ൬1 − ൫1 − ݏ݅݃௧(ݏ)൯ ቀ1 − ߛ௧௦௜௚(ݏ)ቁ൰ ݕ௧௘௟௘௖_௣௢௪௘௥_௔௧_௦௜௚௡௔௟(ݏ), ∀ݐ ∈ ܶ, ݏ ∈ ܵ. (8) 3.1.2 Budget Limitation Constraints (9) are the budget constraints, which limit the number of mitigation, preparedness and response actions that can be taken to prevent or ameliorate event impact. Costs include taking mitigation or preparedness actions to: substations (e.g. placing a backup generator), traffic signals (e.g. providing signals with backup solar power), roadway links (e.g. hardening bridges or piers), and repairing damaged substations, traffic signals, roadway links and transmission lines. Costs are also incurred for assigning a police officer to an intersection for the purpose of directing traffic. That taking pre-event actions can reduce the cost of some recovery actions is 24 captured by way of parameters that connect such activities: ߣ௦௨௕, ߣ௦௜௚, and ߣ௟௜௡௞. ෍ ݉௘௦௨௕ߚ௘௦௨௕ ௘ + ෍ ݊௘௦௨௕ߛ௘௦௨௕(ݏ) ௘ + ෍൫݊௘௣_௦௨௕ − ݊௘௦௨௕൯ߣ௦௨௕ߚ௘௦௨௕ߛ௘௦௨௕(ݏ) ௘ + ෍ ݉௧௦௜௚ߚ௧௦௜௚ ௧ + ෍ ݊௧௦௜௚ߛ௧௦௜௚(ݏ) ௧ + ෍൫݊௧௣_௦௜௚ − ݊௧௦௜௚൯ߣ௦௜௚ߚ௧௦௜௚ߛ௧௦௜௚(ݏ) ௧ + ෍ ݉௩௟௜௡௞ߚ௩௟௜௡௞ ௩ + ෍ ݊௩௟௜௡௞ߛ௩௟௜௡௞(ݏ) ௩ + ෍൫݊௩௣_௟௜௡௞ − ݊௩௟௜௡௞൯ߣ௟௜௡௞ߚ௩௟௜௡௞ߛ௩௟௜௡௞(ݏ) ௩ + ෍ ݊௟௧௥௔௡௦ߛ௟௧௥௔௡௦(ݏ) ௟ + ෍ ݊௧௣௢௟௜௖௘ߛ௧௣௢௟௜௖௘(ݏ) ௧ ≤ ܤ, ∀ݏ ∈ ܵ. (9) 3.1.3 Traffic Flow and Link Capacities Constraints (10)-(11) determine path flows between O-D pairs. Constraints (12) compute the new capacity of link v for each scenario s considering the resilience enhancing actions taken to that link. For simplicity, any mitigative action is presumed to ensure the protection of half of the link’s capacity, but a recovery action will return the capacity to its initial value. Link flows are assumed to be continuous variables with no preset upper capacity limit. ݔ௔(ݏ) = ෍ ෍ ߜ௔,௞௪ ݎ௞௪(ݏ) ௞∈௄ೢ௪∈ௐ , ∀ܽ ∈ ܣ, ݏ ∈ ܵ, (10) ෍ ݎ௞௪(ݏ) ௞∈௄ೢ = ݍ௪, ∀ݓ ∈ ܹ, ݏ ∈ ܵ. (11) ܥ௩௡௘௪(ݏ) = ܥ௩ − ∆ܥ௩௣൫1 − ݈݅݊݇௩(ݏ)൯ ቀ1 − ߛ௩௟௜௡௞(ݏ)ቁ − ൫∆ܥ௩ − ∆ܥ௩௣൯൫1 − ݈݅݊݇௩(ݏ)൯(1 − ߚ௩௟௜௡௞) ቀ1 − ߛ௩௟௜௡௞(ݏ)ቁ, ∀ݒ ∈ ܸ, ݏ ∈ ܵ. (12) 3.1.4 KKT Conditions The KKT conditions associated with a user equilibrium traffic assignment (Beckman 25 et al., 1956) in a lower-level problem are given by constraints (13)-(15). The uniqueness of the solution to the equivalent UE problem, in which KKT conditions are used, is guaranteed if the following conditions hold: ߲ݐ௔(∙) ߲ݔ௕⁄ = 0 for ܽ ≠ ܾ and ݀ݐ௔(ݔ௔) ݀ݔ௔⁄ > 0, ∀ ܽ (Sheffi, 1985), for ݐ௔(∙) and ݔ௔ the link performance function and traffic flows on link ܽ, respectively. Larsson and Patriksson (1995) proved that the KKT conditions are both necessary and sufficient for optimality in a bilevel program with a UE formulation at the lower level. ݎ௞௪(ݏ) ∙ ൫݌௞௪(ݏ) − ߨ௪(ݏ)൯ = 0, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (13) ݌௞௪(ݏ) − ߨ௪(ݏ) ≥ 0, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (14) ݎ௞௪(ݏ) ≥ 0, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ. (15) 3.1.5 Link Travel Times Link travel times are computed through constraints (16) and (17). For simplicity, these constraints are written assuming each link terminates in a traffic signal. The link travel time functions consist of two components: the well-known Bureau of Public Roads (BPR) function and additional delay. The BPR function captures the travel time due to vehicle movements under recurrent conditions. Additional delay (݈݀݁ܽݕ௔ௗ௢_௡௢௧௛௜௡௚) is included to account for the effects on traffic of outages at the signals. If a signal is operative (i.e. ݏ݅݃௧௙௜௡௔௟(ݏ) = 1) or a police officer is assigned to regulate traffic through the corresponding intersection, the additional delay is reduced to 0 or ݈݀݁ܽݕ௔௣௢௟௜௖௘, respectively. 26 ݐ௔(ݏ) = ݐ௔଴ ൭1 + 0.15 ቆ ݔ௔(ݏ) ܥ௔(ݏ)ቇ ସ ൱ + ݈݀݁ܽݕ௔ௗ௢_௡௢௧௛௜௡௚ ൭1 − ෍ ௔ܰ,௧ݏ݅݃௧௙௜௡௔௟(ݏ) ௧ ൱ + ൫݈݀݁ܽݕ௔௣௢௟௜௖௘ − ݈݀݁ܽݕ௔ௗ௢_௡௢௧௛௜௡௚൯ ൭෍ ௔ܰ,௧ߛ௧௣௢௟௜௖௘(ݏ) ௧ ൱ ൭1 − ෍ ௔ܰ,௧ݏ݅݃௧௙௜௡௔௟(ݏ) ௧ ൱, ∀ܽ ∈ ܣ − ܸ, ݏ ∈ ܵ, (16) ݐ௩(ݏ) = ݐ௩଴ ൭1 + 0.15 ቆ ݔ௔(ݏ) ܥ௩௡௘௪(ݏ)ቇ ସ ൱ + ݈݀݁ܽݕ௩ௗ௢_௡௢௧௛௜௡௚ ൭1 − ෍ ௩ܰ,௧ݏ݅݃௧௙௜௡௔௟(ݏ) ௧ ൱ + ൫݈݀݁ܽݕ௩௣௢௟௜௖௘ − ݈݀݁ܽݕ௩ௗ௢_௡௢௧௛௜௡௚൯ ൭෍ ௩ܰ,௧ߛ௧௣௢௟௜௖௘(ݏ) ௧ ൱ ൭1 − ෍ ௩ܰ,௧ݏ݅݃௧௙௜௡௔௟(ݏ) ௧ ൱, ∀ݒ ∈ ܸ, ݏ ∈ ܵ. (17) 3.1.6 Link Status Constraints (18) determine the final link states. If a link is either undamaged by the event (i.e. ݈ ݅݊݇௩(ݏ) = 1) or at least one resilience enhancing action was taken on it (i.e. ߚ௩௟௜௡௞ = 1 or ߛ௩௟௜௡௞(ݏ) = 1), it will be set as “up.” Some set of links are always operative (i.e ݈݅݊݇௔௙௜௡௔௟(ݏ) = 1) as set by constraints (19); they do not belong to the vulnerable set of links for the given scenario type. Additional constraints can be included to prevent the model from taking preparedness or recovery actions on functioning links when excess budget is available, e.g. ∀ݒ ∈ ܸ, ݏ ∈ ܵ: ݈݅݊݇௩(ݏ) + ߛ௩௟௜௡௞(ݏ) ≤ 1, and likewise, ݈݅݊݇௩(ݏ) + ߚ௩௟௜௡௞ ≤ 1. ݈݅݊݇௩௙௜௡௔௟(ݏ) = 1 − ൫1 − ݈݅݊݇௩(ݏ)൯ ∙ (1 − ߚ௩௟௜௡௞) ∙ ቀ1 − ߛ௩௟௜௡௞(ݏ)ቁ, ∀ݒ ∈ ܸ, ݏ ∈ ܵ, (18) ݈݅݊݇௔௙௜௡௔௟(ݏ) = 1, ∀ܽ ∈ ܣ − ܸ, ݏ ∈ ܵ. (19) 27 3.1.7 Repair Operations Limitations Constraints (20) determine which paths from the depot to the location of the affected components are open. Repair operations can only be performed if at least one open path is available for the repair crew to reach the affected area (constraints (21) to (23)). It is assumed that all repair actions can be completed instantaneously as long as the sites are accessible (constraints (20) to (23)). ൭෍ ∆௔,௞௡ ݈݅݊݇௔௙௜௡௔௟(ݏ) ௔∈஺ − ෍ ∆௔,௞௡ ௔∈஺ ൱ ݌ܽݐℎ௞௡(ݏ) = 0, ∀݊ ∈ ܰ, ݇ ∈ ܭ௡, ݏ ∈ ܵ, (20) ߛ௘௦௨௕(ݏ) ≤ ෍ ቌܩ௘,௡ ෍ ݌ܽݐℎ௞௡(ݏ) ௞∈௄೙ ቍ ௡∈ே , ∀݁ ∈ ܧ, ݏ ∈ ܵ, (21) ߛ௧௦௜௚(ݏ) ≤ ෍ ቌܫ௧,௡ ෍ ݌ܽݐℎ௞௡(ݏ) ௞∈௄೙ ቍ ௡∈ே , ∀ݐ ∈ ܶ, ݏ ∈ ܵ, (22) ߛ௟௧௥௔௡௦(ݏ) ≤ ෍ ቌ ௟ܱ,௡ ෍ ݌ܽݐℎ௞௡(ݏ) ௞∈௄೙ ቍ ௡∈ே , ∀݈ ∈ ܮ, ݏ ∈ ܵ. (23) Binary integrality is enforced through the remaining constraints: ߚ௘௦௨௕ ∈ ሼ0,1ሽ, ∀݁ ∈ ܧ ߚ௧௦௜௚ ∈ ሼ0,1ሽ, ∀ݐ ∈ ܶ ߚ௩௟௜௡௞ ∈ ሼ0,1ሽ, ∀ݒ ∈ ܸ ߛ௘௦௨௕(ݏ) ∈ ሼ0,1ሽ, ∀݁ ∈ ܧ, ݏ ∈ ܵ ߛ௧௦௜௚(ݏ) ∈ ሼ0,1ሽ, ∀ݐ ∈ ܶ, ݏ ∈ ܵ ߛ௩௟௜௡௞(ݏ) ∈ ሼ0,1ሽ, ∀ݒ ∈ ܸ, ݏ ∈ ܵ ߛ௧௣௢௟௜௖௘(ݏ) ∈ ሼ0,1ሽ, ∀ݐ ∈ ܶ, ݏ ∈ ܵ ߛ௟௠௔௜௡_௧௥௔௡௦(ݏ) ∈ ሼ0,1ሽ, ∀݈ ∈ ܮଵ, ݏ ∈ ܵ ߛ௟௦௘௖௢௡ௗ௔௥௬_௧௥௔௡௦(ݏ) ∈ ሼ0,1ሽ, ∀݈ ∈ ܮଶ, ݏ ∈ ܵ 28 3.2 Linear approximation The resilience formulation is highly non-linear and non-convex. Nonlinear constraints associated with complementarity and multi-linear terms can be replaced with equivalent linear equations, although with the addition of binary variables. This is described in Subsections 3.2.3 and 3.2.4. Obtaining a globally optimal solution to this equivalent problem proved to be impractical, in part because of remaining nonlinearity in the objective function. Thus, the application of linear approximation techniques for this purpose is suggested (Subsections 3.2.1 and 3.2.2). 3.2.1 Linearizing the objective function Objective function (1) seeks to minimize the expected total system travel time over all scenarios using link travel times that are a function of link flows. This creates a non- linear and non-convex function. An equivalent linear function (26) can replace objective function (1). This equivalency was shown in (Wang and Lo, 2010) and is extended here to multiple scenarios. As for every scenario a user equilibrium assumption is made, O-D travel times along used paths are thus identical at ߨ௪(ݏ). Given an inelastic demand assumption, the expected total system travel time can be rewritten in terms of constant O-D demand, ݍ௪, and O-D travel time, ߨ௪(ݏ), as in (24). ܯ݅݊ ܼ = ܧ௦ ൥ ෍ ݍ௪ߨ௪(ݏ) ௪∈ௐ ൩ (24) 3.2.2 Linearizing the BPR function The relationship between flows and travel times is captured in Constraints (16) and 29 (17) using the BPR function. The BPR function is a quartic, bivariate function. Numerous earlier works have presented techniques for linearizing this function; however, in these works capacities are constant terms. Here, capacities may vary under potential hazard impact events. Moreover, they are discrete, taking on one of three values (0, half of full capacity, and full capacity) and decision-dependent (a function of chosen mitigative and recovery actions). Thus, to linearize the BPR function, it is essential to partition the feasible domain of link flows, ݔ௔, into smaller portions. Following Wang and Lo (2010), the feasible domain of flows along each link (ݔ௔(ݏ)) is partitioned into Φ small regions: ܺ௔ఝ ≤ ݔ௔(ݏ) < ܺ௔ఝାଵ, ∀ܽ ∈ ܣ, ݏ ∈ ܵ, (25) where ܺ௔߮’s are pre-specified parameters (߮ = 1,2, … , Φ − 1). The feasible domain of capacity ܥ௩௡௘௪(ݏ), however, consists of three possible values: 0, ܥ௔/2, and ܥ௔. That is, the entire region is divided into Φ*3 small regions. The non-linear BPR function then can be approximated by a first-order Taylor series for each of these regions: ̃ݐ௔(ݏ) = ݐ௔(ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦) + ݐ௔ᇱ (ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦) ∗ ൫ݔ௔(ݏ) − ܺ௔ ఝ൯ = ݐ௔(ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦) − ቀݐ௔ᇱ (ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦)ቁ ∗ ൫ܺ௔ ఝ൯ + ቀݐ௔ᇱ (ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦)ቁ ∗ ൫ݔ௔(ݏ)൯ = ܣ௔ఝ,ఎ + ܤ௔ఝ,ఎ ∙ ݔ௔(ݏ), (26) where ̃ݐ௔(ݏ) approximate travel time, ݐ௔ᇱ (ݏ) first derivative of ݐ௔(ݏ) with respect to ݔ௔(ݏ), and 30 ܣ௔ఝ,ఎ, ܤ௔ఝ,ఎ pre-specified parameters equal to ݐ௔(ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦) − ቀݐ௔ᇱ (ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦)ቁ ∗ ൫ܺ௔ఝ൯ and ݐ௔ᇱ (ݏ)|௑ೌക,஼ೡ೙೐ೢ(௦), respectively. Through constraints (27), if ݔ௔(ݏ) ≥ ܺ௔ఝ then ߙ௔ఝ(ݏ) = 0, and if ݔ௔(ݏ) < ܺ௔ఝ then ߙ௔ఝ(ݏ) = 1. −ܯ ∙ ߙ௔ఝ(ݏ) ≤ ݔ௔(ݏ) − ܺ௔ఝ ≤ ܯ ∙ ቀ1 − ߙ௔ఝ(ݏ)ቁ − ߝ, ∀ܽ ∈ ܣ, ݏ ∈ ܵ, ߮ = 1,2, … (27) ߤ௔ఝ(ݏ) = ߙ௔ఝାଵ(ݏ) − ߙ௔ఝ(ݏ), ∀ܽ߳ܣ, ݏ߳ܵ, ߮ = 1,2, … (28) Constraints (27) and (28) together determine the region in which ݔ௔(ݏ) falls: ൞ ܺ௔ఝ ≤ ݔ௔(ݏ) < ܺ௔ఝାଵ ሯልሰ ߙ௔ఝ(ݏ) = 0, ߙ௔ఝାଵ(ݏ) = 1, ܺ௔ఝାଵ ≤ ݔ௔(ݏ) ሯልሰ ߙ௔ఝ(ݏ) = 0, ߙ௔ఝାଵ(ݏ) = 0, ݔ௔(ݏ) < ܺ௔ఝ ሯልሰ ߙ௔ఝ(ݏ) = 1, ߙ௔ఝାଵ(ݏ) = 1. For the first case, as shown, ݔ௔(ݏ) lies in the range ൣܺ௔ఝ, ܺ௔ఝାଵ൯, and according to constraints (29), ߤ௔ఝ(ݏ) = 1. However, for the second and third cases in which ݔ௔(ݏ) lies outside range ൣܺ௔ఝ, ܺ௔ఝାଵ൯, ߤ௔ఝ(ݏ) = 0. As capacities are discrete, this linearization approach must be adapted. Constraints (29) determine into which group capacity falls. Constraints (30) restrict the capacity to be in only one of the groups. ܥ௔௡௘௪(ݏ) = ߩ௔ଵ(ݏ) ∙ (0) + ߩ௔ଶ(ݏ) ∙ ൬ ܥ௔ 2 ൰ + ߩ௔ ଷ(ݏ) ∙ (ܥ௔), ∀ܽ ∈ ܣ, ݏ ∈ ܵ, (29) ߩ௔ଵ(ݏ) + ߩ௔ଶ(ݏ) + ߩ௔ଷ(ݏ) = 1, ∀ܽ ∈ ܣ, ݏ ∈ ܵ. (30) If both ߤ௔ఝ(ݏ) and ߩ௔ఎ(ݏ), in which ߟ = 1,2, ݋ݎ 3, equal one, then based on constraints (31), ߬௔ఝ,ఎ(ݏ) will be 2; otherwise ߬௔ఝ,ఎ(ݏ) is 1 or zero. ߬௔ఝ,ఎ(ݏ) then will 31 be used in constraints (32) to determine the approximate travel time, ̃ݐ௔(ݏ). In constraints (32), ߬௔ఝ,ఎ(ݏ) equals 2, forcing ̃ݐ௔(ݏ) to be equal to ܣ௔ఝ,ఎ + ܤ௔ఝ,ఎ ∙ ݔ௔(ݏ). ߬௔ఝ,ఎ(ݏ) = ߤ௔ఝ(ݏ) + ߩ௔ఎ(ݏ), ∀ܽ ∈ ܣ, ݏ ∈ ܵ, ߮ = 1,2, … , ߟ = 1,2,3. (31) −ܯ ∙ ቀ2 − ߬௔ఝ,ఎ(ݏ)ቁ ≤ ̃ݐ௔(ݏ) − ቀܣ௔ఝ,ఎ + ܤ௔ఝ,ఎ ∙ ݔ௔(ݏ)ቁ ≤ ܯ ∙ ቀ2 − ߬௔ఝ,ఎ(ݏ)ቁ , ∀ܽ ∈ ܣ, ݏ ∈ ܵ, ߮ = 1,2, … , ߟ = 1,2,3. (32) In short, given a link’s flow-capacity settings, travel time is computed based on the relevant segment in the linear approximation of the BPR function. A more precise approximation can be obtained by dividing the feasible domain of link flows, ݔ௔, into very small portions. Doing so, however, will increase the number of variables and running times. 3.2.3 Linearizing complementarity constraints Two sets of complementarity constraints must be linearized, the first of which is associated with replacing the lower-level problem with its KKT conditions and the second of which is associated with repair availability. Constraints (13)-(15) are replaced with equivalent constraints (33)-(37). Their equivalencies are shown in (Fortuny-Amat and McCarl, 1981). In constraints (33), if ݕ௞௪(ݏ) = 0, then ݎ௞௪(ݏ) will be zero, and travel time of path ݇ connecting O-D pair ݓ, ݌௞௪(ݏ), can take any positive value (constraint (33)). On the other hand, if ݕ௞௪(ݏ) = 1, then ݎ௞௪(ݏ) will be any positive value, and ݌௞௪(ݏ) will be equal to ߨ௪(ݏ) according to constraints (34). These conditions represent traffic flows that are at a user equilibrium. ݎ௞௪(ݏ) ≤ ܯ ∙ ݕ௞௪(ݏ), ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (33) 32 ൫݌௞௪(ݏ) − ߨ௪(ݏ)൯ ≤ ܯ ∙ ൫1 − ݕ௞௪(ݏ)൯, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (34) ݌௞௪(ݏ) − ߨ௪(ݏ) ≥ 0, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (35) ݎ௞௪(ݏ) ≥ 0, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ, (36) ݕ௞௪(ݏ) ∈ ሼ0,1ሽ, ∀݇ ∈ ܭ௪, ݓ ∈ ܹ, ݏ ∈ ܵ. (37) Using similar logic, constraints (20) are replaced with constraints (38) and (39): ൭෍ ∆௔,௞௡ ݈݅݊݇௔௙௜௡௔௟(ݏ) ௔∈஺ − ෍ ∆௔,௞௡ ௔∈஺ ൱ ≤ ܯ ∙ ݕ௞௡(ݏ), ∀݊ ∈ ܰ, ݇ ∈ ܭ௡, ݏ ∈ ܵ, (38) ݌ܽݐℎ௞௡(ݏ) + ݕ௞௡(ݏ) ≤ 1, ∀݊ ∈ ܰ, ݇ ∈ ܭ௡, ݏ ∈ ܵ. (39) 3.2.4 Other constraints The binary constraints (2, 3, 5, 7, 8, 9, 12, 18 and relevant portions of 16 and 17) can be restated as equivalent linear equations. These linear equivalent equations were not originally presented, because they are more difficult to interpret. This method is presented through an example. Consider constraints (2). This equation determines whether or not power can be expected at feeder ݂. If substation ݁ is down (i.e. ݏݑܾ௘(ݏ) = 0), and no recovery or preparedness actions were taken, then ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) must be zero. However, if a recovery or preparedness action was taken, then ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) must be one (ܯ௘,௙ determines which substation provides power for the feeder under consideration). An equivalent linear form is thus given in (40). This constraint states that if substation ݁ goes down (i.e. ݏݑܾ௘(ݏ) = 0) and no recovery or preparedness action was taken, then ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) is zero. If, on the other hand, at least one of preparedness or recovery action was taken, then this constraint states that 33 ݕ௧௘௟௘௖_௣௢௪௘௥(ݏ) ≤ 1 or 2. Since the objective seeks a minimum solution, ݕ௧௘௟௘௖_௣௢௪௘௥(ݏ) will be set to one. ݕ௙௘௟௘௖_௣௢௪௘௥(ݏ) ≤ ෍ ܯ௘,௙ݏݑܾ௘(ݏ) ௘ + ෍ ܯ௘,௙ߚ௘௦௨௕ ௘ + ෍ ܯ௘,௙ߛ௘௦௨௕(ݏ) ௘ , ∀݂ ∈ ܨଵ, ݏ ∈ ܵ. (40) Other constraints can be linearized using similar logic. 34 Chapter 4: Illustrative Example 4.1 Case study To demonstrate its applicability and provide a numerical example, the proposed model was applied on a network representation built from a real-world coupled electric power- traffic system in a section of Minneapolis, Minnesota. Power is generated, transmitted and distributed to end users through a three-stage process depicted in Figure 2. In the first stage, power is generated at a power plant through the use of fossil fuels, such as coal, oil, and natural gas, or renewable sources, including solar, wind, and hydropower. Figure 2- Simplified electric power system To transmit the power to spatially disparate end-user locations, the power is transmitted at a high voltage using power transformers at transmission (step-up) substations to reduce losses incurred during transmission. It is later decreased to a lower voltage at distribution substations and then distributed to end users along transmission lines. A power drum located near the end users further reduces the voltage to 120V (in the U.S.) for normal household and ordinary business uses. The model depicts the power 35 distribution stage, which involves the distribution (step-down) substations, transmission lines (held up by power poles or buried underground), and end users. The chosen geographic location for the case study is depicted in Figure 3, and the network representation of the roadway network is shown in Figure 4. Only major and minor arterial links, along with their intersections, all of which are signalized, are included. Tables 2 and 3 list the link attributes and OD-based demand estimates, respectively. Figure 3- Case Study Area (South Minneapolis), map created using ESRI’s ArcGIS® 10.3 Figure 4- Roadway network with link IDs 36 Table 2- Link Attributes Link ID Free flow travel time, minutes (ݐ௔଴) Capacity, vehicles per hour (ܥ௔) 1 0.33 1500 2 0.33 1500 3 0.62 1500 4 0.62 1500 5 0.75 1500 6 0.75 1500 7 0.75 1500 8 0.75 1500 9 0.94 3000 10 0.94 3000 11 1.49 1500 12 1.49 1500 13 1.42 5400 14 1.42 5400 15 1.68 1500 16 1.68 1500 17 1.40 1500 18 1.40 1500 19 0.34 1500 20 0.34 1500 Table 3- O-D pair details O-D pair ID Origin node Destination node Demand, vehicles per hour 1 1 8 3000 2 6 3 3000 This portion of Minneapolis is primarily fed by four main substations: Southtown, Aldrich, Elliot Park and Main Street (Figure 5). These substations serve 23, 12, 3, and 1 feeders, respectively, along transmission lines. The coupling of traffic and power networks arises from the power needs of the traffic signals, which are end- 37 users in the power network, and access for repair operations associated with a damaged power network. The case study region is served by the Southtown substation and involves 5 feeders with 13 transmission lines. A single repair crew is presumed to be located at an intersection (node 6) and, for simplicity of example, is capable of completing repairs to either system. The coupled network representation is presented in Figure 6. The coupled system was evaluated under four hypothetical scenarios, each with different affected components (substation, traffic signal, transmission line, or roadway link). Components are assumed to be up or down. Damage is depicted through reduction in roadway link capacities, introduction of travel delays due to signal loss (whether from power outage or physical damage), and power loss to the substation or inability to transmit power due to physical damage to transmission lines. Affected components under each scenario are highlighted in Figure 7. Appendix A provides a table of damage level by component for each scenario. 38 Figure 5- Substations Service Areas (Zima, 2009) Figure 6- Simplified Transportation-Power Coupled Network 39 Figure 7- 4 scenarios (damaged components in dashed lines) 4.2 Experimental Design The resilience of the coupled network was evaluated under a variety of settings, including varying levels of budget ranging from 0 to $130,000 at $10,000 increments and different repair options (repairs to both systems, repairs to only the power network, repairs to only the transportation network and those that preclude a specific repair type). This required 44 runs of the model given the possibility of any of the four scenarios arising with equal probability. An additional run of the model was completed under a 40 no-damage state to assess the performance of the coupled system under normal conditions. This assessment was used to provide a baseline for the analysis and resilience computations. To demonstrate the importance of considering a stochastic setting, an additional four runs of the model were completed, each on a single, deterministically known scenario of the four potential scenarios. 4.3 Analysis of Run Results Run results provide network-level resilience estimates by budget level (Figure 8), performance of the coupled system wherein expenditures are limited to only one network (Figure 9), and performance under restricted repair situations (Figure 10). Figure 8 demonstrates the impact of budget size on performance of the coupled system. As expected, performance increases with greater investment and the rate of increase levels out at higher budget levels. The system returns to the pre-event performance level (i.e. a resilience level of 1.0) at a budget of $130,000 despite that remaining damage persists in the power network. 41 Figure 8- Resilience by budget level Table 4- Total post-disaster unmet power demand by scenario and budget level Budget ($1,000s) Scenario 1 2 3 4 0 37.5% 50.0% 12.5% 100.0% 20 25.0% 12.5% 0.0% 100.0% 40 12.5% 0.0% 0.0% 37.5% 60 0.0% 0.0% 0.0% 25.0% 80 12.5% 0.0% 0.0% 50.0% 100 0.0% 0.0% 0.0% 37.5% 120 0.0% 0.0% 0.0% 25.0% 130 12.5% 0.0% 0.0% 37.5% In a deeper investigation of power network performance, unmet demand in terms of end-user power needs is considered for each possible scenario (Table 4) given resilience-enhancing actions taken for the multi-hazard problem. For the purpose of this analysis, an equal power demand is associated with each intersection (a power consumption node in the power network), representing the demand of both the traffic 42 control devices at that intersection and nearby end-users. In scenarios 2 and 3, performance of the power network improves with increasing budget level; however, this is not the case for scenarios 1 and 4 wherein increasing the budget improves traffic network performance but results in no significant reduction in unmet demand for the power network. This may be explained as follows. Under scenarios 1 and 4, the need for power to the traffic signals is eliminated through the application of alternative energy sources (e.g. solar panels and back-up batteries) at the individual intersections. Such practices are only possible at higher budget levels due to high equipment costs. Figure 9 provides resilience estimates for each budget increment under three expenditure-related options: (1) investments made to only the traffic network; (2) investments made to only the power network; and (3) investments applied across networks with a goal of optimal traffic performance. The former two options depict a special situation wherein network operators of these two systems work in isolation spending the available budget to maximize the resilience level of the transportation network. The results show that for the given hypothetical scenarios, investment in the transportation network is most critical, and using some budget for the power network is most important at lower budget levels. Since the traffic network relies on power for only the operation of its traffic signals (whose loss causes travel delays), and given the option to add alternative (e.g. solar) power to each intersection through pre-event investment, the higher the budget, the less reliant the coupled system is on the power network. Similar behavior was noted in the investigation under individual scenarios in Table 4. Under other scenarios or a reduced set of investment options, where it may not 43 be possible to fully restore traffic-network performance without repairs to the power network, the impact of investment in the power network will be more crucial. Figure 9- Resilience by strategy: distributing budget between networks Table 5- Total post-disaster unmet power demand by scenario with budget available only to transportation network Budget Scenario 1 2 3 4 0 37.5% 50.0% 12.5% 100.0% Table 6- Total post-disaster unmet power demand by scenario and budget level (in $1,000s) with budget available only to power network Budget ($1,000s) Scenario 1 2 3 4 0 37.5% 50.0% 12.5% 100.0% 20 37.5% 37.5% 0.0% 62.5% 40 0.0% 0.0% 0.0% 50.0% 60 0.0% 0.0% 0.0% 50.0% 80 0.0% 0.0% 0.0% 0.0% 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 20 40 60 80 100 120 140 Re sil ien ce Budget ($1,000s) Both networks Transportation only Power only 44 100 0.0% 0.0% 0.0% 0.0% 120 0.0% 0.0% 0.0% 0.0% 130 0.0% 0.0% 0.0% 0.0% To provide additional insight, the performance of the power network in terms of unmet demand where the budget is applied to only the transportation network or the power network, but not both, was studied (Tables 5 and 6). The tables show that unmet power demand remained constant for all budget levels when the total budget is applied exclusively to the transportation network (Table 5). Moreover, despite that there is no improvement in transportation system performance when the budget is dedicated to the power network (Table 6), unmet power demand was greatly diminished with greater available budget despite an investment objective that aims to improve traffic network performance. Figure 10 presents system resilience level under limited repair operations. The figure shows that traffic signals have the greatest impact on travel times, and thus their operability, should be prioritized. While generally the operability of transportation links directly influences travel time, there is no scenario considered herein in which damage to links causes a situation that changes path choice or that significantly impacts connectivity. Of course, these results are specific to the example scenarios designed herein, and it might be the case in some situations that transportation links (power equipment) have the greatest impact for the performance of the coupled system. Next, resilience-enhancing actions are chosen under individual scenarios, creating four independent, deterministic optimization problems. Results from runs of these scenario-specific models for a budget of $40,000 are given in Figure 11 under 45 “deterministic runs.” The figure indicates that a fully-functional coupled network (with a focus on the traffic network) is achieved under scenarios 1 and 3, but performs poorly under scenario 4. In this latter scenario, the budget is not large enough to counter the impacts of the more extreme event depicted through this scenario. These sets of runs show the sensitivity of a resilience index to the scenario specification. Thus, resilience to an uncertain future may be under- or over-estimated by considering a single scenario, warranting the need for a stochastic approach. Figure 10- Resilience level under restricted repair opportunities The resilience level when taking resilience-enhancing actions to achieve the optimal expected performance (i.e. the stochastic model) is 0.633 (on a scale of 0 to 1). This can be compared to the average of four resilience levels 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 40 80 120 160 Re sil ien ce Budget ($1,000) no repair to signals no repair to transportation links no repair to substations no repair to transmission lines optimal solution 46 ((1.0+0.821+1+0.341)/4=0.790), each obtained from solution of the deterministic problem assuming perfect information about the scenario. The difference between these two values is 0.157 and is defined as the expected value of perfect information (EVPI). Converting the value of resilience to an equivalent cost, the EVPI can be interpreted as the maximum amount of money that transportation managers should be willing to pay for perfect predictions of future hazard events and their impacts. For this purpose, a monetary conversion of total travel time using value-of-time estimates for drivers can be obtained. The common value of the stochastic solution (VSS) cannot be obtained given the binary nature of damage impact under each scenario. However, how far from optimal the solutions would be if pre-event preparedness/mitigative actions were taken assuming the occurrence of only one of the possible scenarios but allowing for post- event (repair) actions under whichever scenario is realized can be considered. Practically, optimal first-stage (mitigative/preparedness) decisions from each of the four deterministic optimization problems described in the previous paragraph are fixed, creating four new stochastic models with only second-stage options. In comparing these results in Figure 11 (“fixed pre-event actions”), it is noted that if first-stage decisions are taken to hedge against only scenario 4, the resilience level given equal probability of any of the scenarios actually arising would fall to 0.511 from 0.633 (i.e. by 12.2 percentage points). Results from runs of each of these models assuming a budget of $40,000 for both first and second-stage actions are provided in Figure 11. At other budget levels, first-stage decisions may vary more drastically for each of the 47 deterministic problem instances. A similar set of runs completed with a budget of $80,000 shows this difference using scenario 4 as the base for determining the first- stage decision to be 23.2 percentage points. At other budget levels this difference may be smaller. By definition, however, resilience will be largest if first-stage decisions are flexible (unconstrained) and aim to hedge against all possible futures, and not only the worst-case. Figure 11- The value of considering stochasticity and perfect information (Budget=$40,000) The results provided in this chapter are based on the hypothetical damage scenarios and resulting damage impact (e.g. added delays). The main purpose of this chapter was to assess and demonstrate the applicability of the proposed modeling approach for coupled lifelines though a detailed numerical example. The application of the model showed that to obtain the highest resilience possible, the shared budget must be distributed across lifelines, i.e. both power and transportation networks. The results 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 Re sil ien ce Scenario Deterministic run Original two-stage stochastic problem Resilience with fixed pre-event actions 48 also showed how the resilience of the transportation systems (a roadway network here) could be over- or under-estimated by: (1) disregarding the impact of damage to the power network or the effect of repair operations performed on its damaged components or (2) by assuming the possibility of only one damage scenario. 49 Chapter 5: Conclusions, Limitations and Extensions Capturing the interdependencies between the coupled traffic and power distribution networks in transportation resilience quantification and maximization is critical. This work provides a mathematical approach employing intersystem variables and coupling equations based on logical intersystem connections to capture these interdependencies and investigate coupled-system performance under multiple hazards. Generally speaking, interconnectivity variables and equations fall into one of four categories: node-to-node (electric power present at traffic signals), node-to-link (loss of power demand from traffic signals may lead to imbalances in the power distribution network and ultimately loss of electric power along a transmission line), link-to-node (repair to damaged components located at a node requires a set of links with reasonable travel times), and link-to-link (electric power required for rail-line operations) connections. A review of the literature indicates that prior published works involving coupled transportation systems have focused primarily on vulnerability assessment and restoration. This work provides a methodology for resilience measurement. It integrates identification of pre- and post-event actions for optimizing coupled-transportation- system performance under multiple hazard event possibilities. Such a comprehensive, quantitative approach is absent from prior works in the published literature. A number of potential improvements or extensions may be of interest. In particular, an exact decomposition method might be applied that would decompose the large MIP into smaller MIPs. It may be possible then to take advantage of parallel 50 processing in its solution. Exact solution via integer L-shaped decomposition may also be promising for the proposed problem. For large, real-world instances, a heuristic could solve larger problem instances considered under significantly more scenarios than explored in the case study herein. Solution via a commercial solver or other exact technique can provide a benchmark for evaluating the solution quality of such a heuristic on small instances. Herein, a single repair team is presumed to be present at a single, known location and capable of all repair activities. In a second extension, one might consider multiple, heterogeneous repair teams that are stochastically located over the network. Furthermore, repairs are assumed to be completed instantaneously if the repair crew can access the location. Time for traveling to the repair site and service times could be included in a third extension. Such consideration would necessitate the need for a time- dependent network representation such as was employed in (Zhang and Miller-Hooks, 2014) in the context of resilience quantification and optimization for a single (uncoupled) transportation system. Alternatively, a multistage stochastic program could be adopted. In a fourth possible extension of this work, an objective function that explicitly considers unmet power demand may be of interest. A single, additive function of total travel time and unmet power demand may be employed or, alternatively, a multi- objective or goal-programming approach may be desirable. A last extension might involve a more detailed power flow model. The remainder of this chapter provides such an extension to the proposed model in which a 51 well-known, linear direct current (DC) power flow approach is applied to approximate actual power flows (Andersson, 2004). Such an approach would enable connections between loss of power demand and a power outage that are not required for this application, but might be useful in a larger, urban context. Notation Sets ܦ set of power nodes including substations, ݁, and signals, ݐ, and slack bus, ߰; ܦ ⊆ ܷ Ψ set of slack buses Parameters ܤௗ,ௗᇲ susceptance matrix; = ∑ ൫ܪ௟,ௗ ∙ ܪഥ௟,ௗᇲ൯௟∈௅ , ∀݀, ݀ᇱ ∈ ܦ ܪഥ௟,ௗ network transfer matrix; = ோ௘௔௖௧௔௡௖௘೗ඥோ௘௔௖௧௔௡௖௘೗ାඥோ௘௦௜௦௧௔௡௖௘೗ ∙ ܪ௟,ௗ, ∀݈ ∈ ܮ, ݀ ∈ ܦ ܿܽ݌௟(ݏ) capacity of transmission line ݈ ∈ ܮ under scenario ݏ ∈ ܵ ݏݑܾ_ܿܽ݌௘(ݏ) maximum power generation at substation ݁ ∈ ܧ under scenario ݏ ∈ ܵ ݏݓௗ slack bus vector; = ൜0, if ݀ = ߰ ∈ Ψ,1, otherwise Decision Variables ܲ݋ݓ݁ݎௗ(ݏ) power availability as a consequence of injection and demand at power node ݀ ∈ ܦ under scenario ݏ ∈ ܵ ߠௗ(ݏ) voltage angle at power node ݀ ∈ ܦ under scenario ݏ ∈ ܵ ܧܨ݈݋ݓ௟(ݏ) electric power flow along the transmission line ݈ ∈ ܮ under scenario ݏ ∈ ܵ ܲ݀݁݉ܽ݊݀௧(ݏ) power demand at traffic signal ݐ ∈ ܶ under scenario ݏ ∈ ܵ 52 ܷ݀݁݉ܽ݊݀௧(ݏ) unserved load at traffic signal ݐ ∈ ܶ under scenario ݏ ∈ ܵ ݕ௧(ݏ) auxiliary variable indicating state of shortfall in scenario ݏ ∈ ܵ for node ݐ ∈ ܶ ݏଓ݃തതതത௧(ݏ) binary state of traffic signal ݐ ∈ ܶ under scenario ݏ ∈ ܵ (=1 if up and 0 if down) To calculate power flow resulting from a certain generation-load combination, the DC load flow model requires information on the Power Transfer Distribution Factor (PTDF) (Delaure et al., 2007). The PTDF can be derived from the product of network susceptance matrix ܤௗ,ௗᇲ and voltage angle ߠௗ as in (41). ܲ݋ݓ݁ݎௗ(ݏ) = ∑ ܤௗ,ௗᇲௗᇲ ߠௗᇲ(ݏ) , ∀݀ ∈ ܦ, ݏ ∈ ܵ. (41) The power moving through the transmission lines can be controlled by altering the voltage at a node, the impedance between the nodes and the angle between the terminal voltages. Constraints (42) define the power flow on the transmission lines in terms of their susceptances and phase angles: ܧܨ݈݋ݓ௟(ݏ) = ∑ ܪഥ௟,ௗௗ ߠௗ(ݏ) , ∀݈ ∈ ܮ, ݏ ∈ ܵ. (42) The power variable at substations is limited by the maximum capacity, which depends on the state of substation ݏݑܾ௘(ݏ) and recovery action ߛ௘௦௨௕(ݏ), as well as additional capacity ∆ܿܽ݌ in cases where preparedness action (ߚ௘௦௨௕) is taken. 0 ≤ ܲ݋ݓ݁ݎ௘(ݏ) ≤ ݏݑܾ_ܿܽ݌௘(ݏ)൫ݏݑܾ௘(ݏ) + ߛ௘௦௨௕(ݏ)൯ + ∆ܿܽ݌(ߚ௘௦௨௕), ∀݁ ∈ ܧ, ݏ ∈ ܵ. (43) The flows on the power transmission lines are limited in constraints (44) to (47). Bidirectionality of power flows is taken into consideration. ܧܨ݈݋ݓ௟(ݏ) ≤ ൫݉ܽ݅݊_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ)൯ ∗ ܿܽ݌௟(ݏ), ∀݈ ∈ ܮଵ, ݏ ∈ ܵ. (44) 53 −ܧܨ݈݋ݓ௟(ݏ) ≤ ൫݉ܽ݅݊_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ)൯ ∗ ܿܽ݌௟(ݏ), ∀݈ ∈ ܮଵ, ݏ ∈ ܵ. (45) ܧܨ݈݋ݓ௟(ݏ) ≤ ൫ݏ݁ܿ݋݊݀ܽݎݕ_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ)൯ ∗ ܿܽ݌௟(ݏ), ∀݈ ∈ ܮଶ, ݏ ∈ ܵ. (46) −ܧܨ݈݋ݓ௟(ݏ) ≤ ൫ݏ݁ܿ݋݊݀ܽݎݕ_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ)൯ ∗ ܿܽ݌௟(ݏ), ∀݈ ∈ ܮଶ, ݏ ∈ ܵ. (47) The following constraints limit the application of recovery actions to substations that are damaged. ݏݑܾ௘(ݏ) + ߛ௘௦௨௕(ݏ) ≤ 1, ∀݁ ∈ ܧ, ݏ ∈ ܵ. (47) ݉ܽ݅݊_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ) ≤ 1, ∀݈ ∈ ܮଵ, ݏ ∈ ܵ. (48) ݏ݁ܿ݋݊݀ܽݎݕ_ݐݎܽ݊ݏ௟(ݏ) + ߛ௟௧௥௔௡௦(ݏ) ≤ 1, ∀݈ ∈ ܮଶ, ݏ ∈ ܵ. (49) Constraints (50) account for the impact of preparedness actions on substation send-out capacity enhancement. For a subset of feeders, ܨଵ, and their associated traffic signals, additional capacity, ∆ܿܽ݌, can be added by taking preparedness action ߚ௘௦௨௕. However, for other feeders, (ܨ − ܨଵ), retaining even the initial capacity if the substation is damaged can only be achieved by taking a recovery action as depicted in constraints (50). ݏ݅݃௧௙௜௡௔௟(ݏ) forces power to be zero at those traffic signals that cannot receive power due to direct damage or damage to transmission lines that distribute power or even damage to substation that is supposed to provide power for that signal. Power can be redistributed to other power demand nodes (constraint (50)). 54 ܤ௘,௧ߠ௧(ݏ) ≤ ෍ ൫ܯ௘,௙ ∗ ܳ௙,௧൯ ௙∈ிభ ∗ ݏ݅݃௧௙௜௡௔௟(ݏ) ∗ ቀݏݑܾ_ܿܽ݌௘(ݏ) ∗ ൫ݏݑܾ௘(ݏ) + ߛ௘௦௨௕(ݏ)൯ + ∆ܿܽ݌(ߚ௘௦௨௕)ቁ + ෍ ൫ܯ௘,௙ ∗ ܳ௙,௧൯ ௙∈ிିிభ ∗ ݏ݅݃௧௙௜௡௔௟(ݏ) ∗ ቀݏݑܾ_ܿܽ݌௘(ݏ) ∗ ൫ݏݑܾ௘(ݏ) + ߛ௘௦௨௕(ݏ)൯ቁ , ∀ݐ ∈ ܶ, ݁ ∈ ܧ, ݏ ∈ ܵ. (50) Slack buses are defined in constraints (51) for DC load flows1: −ݏݓௗ ∙ ߠௗ(ݏ) = 0, ∀݀ ∈ ܦ, ݏ ∈ ܵ. (51) Constraints (52) ensure adherence to Kirchhoff’s law of energy conservation. ܷ݀݁݉ܽ݊݀௧(ݏ) = ݏ݅݃௧௙௜௡௔௟(ݏ) ∙ ܲ݋ݓ݁ݎ௧(ݏ) + ܲ݀݁݉ܽ݊݀௧(ݏ), ∀ݐ ∈ ܶ, ݏ ∈ ܵ. (52) Constraints (53) specify power consumed at traffic signal ݐ: ܲ݋ݓ݁ݎ௧(ݏ) ≤ 0, ∀ݐ ∈ ܶ, ݏ ∈ ܵ. (53) Dependencies between substations and signals are modeled through logical constraints (54)-(56). These constraints determine if the unmet demand for power is positive. If it is positive, then no power is available to meet the demand at traffic signal ݐ and traffic signal t will be nonfunctional. ܷ݀݁݉ܽ݊݀௧(ݏ) represents the shortfall in power under scenario s. ݕ௧(ݏ) indicates the state of shortfall in scenario s at traffic signal t. ݏ݅݃௧(ݏ) acts as a control switch for this state. When ܷ݀݁݉ܽ݊݀௧(ݏ) is greater than 0, ݕ௧(ݏ) must be 1. Thus, ݕ௧(ݏ) along with ߚ௧௦௜௚ and ߛ௧௦௜௚(ݏ) determine the final state of this traffic signal t: ݏଓ݃തതതത௧(ݏ). 1Phase angle at slack bus equals 0; this is necessary for tractability within the DC load flow (DCLF) approach. 55 ܷ݀݁݉ܽ݊݀௧(ݏ) ≤ ܯ ∗ ݕ௧(ݏ), ∀ݐ ∈ ܶ, ݏ ∈ ܵ, (54) ܷ݀݁݉ܽ݊݀௧(ݏ) ≥ ݕ௧(ݏ) ∀ݐ ∈ ܶ, ݏ ∈ ܵ, (55) ݏଓ݃തതതത௧(ݏ) = ቀ1 − ݕ௧(ݏ) ∗ ൫1 − ߚ௧௦௜௚൯ቁ ∗ ൬1 − ൫1 − ݏ݅݃௧(ݏ)൯ ∗ ቀ1 − ߛ௧௦௜௚(ݏ)ቁ൰ ∀ݐ ∈ ܶ, ∀ݏ ∈ ܵ. (56) The last set of constraints (56) can be linearized using a similar method employed in Subsection 2.2.4. 56 Appendix A Table 7- Damage level by component for each scenario (1=functional, 0=damaged) Component ID Scenario 1 2 3 4 Substation 1 1 1 1 0 Traffic Signals 4 0 0 0 0 5 0 0 0 0 6 1 0 1 0 8 0 1 0 0 9 1 0 1 0 11 0 1 1 1 12 1 1 0 0 13 1 1 0 1 Roadway Links 14 1 1 0 1 15 1 0 1 0 20 1 0 1 0 21 1 1 0 0 25 1 1 1 0 26 1 1 1 0 27 0 1 0 1 28 1 0 1 1 Transmission Lines 1 1 1 1 0 2 1 0 1 1 4 1 1 1 0 5 0 1 1 1 6 1 1 1 0 10 1 0 1 1 11 1 1 1 0 12 0 1 1 1 13 1 1 0 1 15 0 1 1 1 17 1 1 1 0 18 1 1 1 0 19 1 0 1 1 57 Bibliography Andersson, G. (2004) Modelling and analysis of electric power systems. EEH-Power Systems Laboratory, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland. Arcidiacono, V., Cimellaro, G.P., Reinhorn, A.M. and Bruneau, M. (2012) Community resilience evaluation including interdependencies. In 15th World Conference on Earthquake Engineering (15WCEE) (pp. 24-28). Beckmann M, McGuire CB, Winsten CB. (1956) Studies in the Economics of Transportation. Yale University Press, Connecticut. Bigger, J.E., Willingham, M.G., Krimgold, F. and Mili, L. (2009) Consequences of critical infrastructure interdependencies: lessons from the 2004 hurricane season in Florida. International Journal of Critical Infrastructures, 5(3), pp.199-219. Cavdaroglu, B., Hammel, E., Mitchell, J.E., Sharkey, T.C. and Wallace, W.A. (2013) Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems. Annals of Operations Research, 203(1), pp.279-294. Cui, Y., Liang, D. and Song, L. (2014) Simplified Method for Evaluating the Impact of a Transportation Network on Posthurricane Access to Healthcare Facilities. Journal of Performance of Constructed Facilities, 30(1), p.04014182. Delarue, E., Bekaert, D., Belmans, R. and D’haeseleer, W. (2007) Development of a comprehensive electricity generation simulation model using a mixed integer programming approach. International Journal of Electrical, Computer, and Systems Engineering, 1(2), pp.92-97. Department of Homeland Security website: https://www.dhs.gov/what-security-and- resilience Faturechi, R. and Miller-Hooks, E. (2014) Measuring the performance of transportation infrastructure systems in disasters: a comprehensive review. Journal of Infrastructure Systems, 21(1), p.04014025. Faturechi, R. and Miller-Hooks, E. (2014) Travel time resilience of roadway networks under disaster. Transportation Research Part B: Methodological, 70, pp.47-64. Fortuny-Amat, J. and McCarl, B. (1981) A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, pp.783-792. 58 Gibbons R. (1992) Game Theory for Applied Economists. Princeton University Press, New Jersey. Gong, J., Mitchell, J.E., Krishnamurthy, A. and Wallace, W.A. (2014) An interdependent layered network model for a resilient supply chain. Omega, 46, pp.104- 116. Huang, C.N., Liou, J.J. and Chuang, Y.C. (2014) A method for exploring the interdependencies and importance of critical infrastructures. Knowledge-Based Systems, 55, pp.66-74. Johansson, J. and Hassel, H. (2010) An approach for modelling interdependent infrastructures in the context of vulnerability analysis. Reliability Engineering & System Safety, 95(12), pp.1335-1344. Kajitani, Y. and Sagai, S. (2009) Modelling the interdependencies of critical infrastructures during natural disasters: a case of supply, communication and transportation infrastructures. International Journal of Critical Infrastructures, 5(1-2), pp.38-50. Larsson, T. and Patriksson, M. (1995) An augmented Lagrangean dual algorithm for link capacity side constrained traffic assignment problems. Transportation Research Part B: Methodological, 29(6), pp.433-455. Lee, E.E., Mitchell, J.E. and Wallace, W.A. (2007) Restoration of services in interdependent infrastructure systems: A network flows approach. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 37(6), pp.1303- 1317. Ouyang, M. (2014) Review on modeling and simulation of interdependent critical infrastructure systems. Reliability Engineering & System Safety, 121, pp.43-60. Procyk A, and Dhariwal R. (2010) Transportation Sector Case Study: Characterizing vulnerability to Infrastructure Failure Interdependencies (IFIs) from flood and earthquake hazards. Retrieved from Analyzing Infrastructures for Disaster-Resilient Communities website: http://www.chs.ubc.ca/dprc_koa/ Rinaldi, S.M., Peerenboom, J.P. and Kelly, T.K. (2001) Identifying, understanding, and analyzing critical infrastructure interdependencies. Control Systems, IEEE, 21(6), pp.11-25. Santos-Reyes, J., Padilla-Pérez, D. and Beard, A.N. (2015) Modeling Critical Infrastructure Interdependency: The Case of the Mexico City Metro Transport System. Human and Ecological Risk Assessment: An International Journal, 21(5), 59 pp.1428-1444. Sharkey, T.C., Cavdaroglu, B., Nguyen, H., Holman, J., Mitchell, J.E. and Wallace, W.A. (2015) Interdependent network restoration: On the value of information- sharing. European Journal of Operational Research, 244(1), pp.309-321. Sharkey, T.C., Nurre, S.G., Nguyen, H., Chow, J.H., Mitchell, J.E. and Wallace, W.A. (2015) Identification and classification of restoration interdependencies in the wake of Hurricane Sandy. Journal of Infrastructure Systems, p.04015007. Sheffi Y. (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall, New Jersey. Wang, D.Z. and Lo, H.K. (2010) Global optimum of the linearized network design problem with equilibrium flows. Transportation Research Part B: Methodological, 44(4), pp.482-492. Zhang, J., Song, B., Zhang, Z. and Liu, H. (2014) An approach for modeling vulnerability of the network of networks. Physica A: Statistical Mechanics and its Applications, 412, pp.127-136. Zhang, P. and Peeta, S. (2011) A generalized modeling framework to analyze interdependencies among infrastructure systems. Transportation Research Part B: Methodological, 45(3), pp.553-579. Zhang, X. and Miller-Hooks, E. (2014) Scheduling short-term recovery activities to maximize transportation network resilience. Journal of Computing in Civil Engineering, 29(6), p.04014087. Zima S. (2009) South Minneapolis electric distribution delivery system long-term study. Technical report. Retrieved from Xcel Energy website: https://www.xcelenergy.com/