skip to main content


Title: A Mean-risk Mixed Integer Nonlinear Program for Network Protection
d. Many of the infrastructure sectors that are considered to be crucial by the Department of Homeland Security include networked systems (physical and temporal) that function to move some commodity like electricity, people, or even communication from one location of importance to another. The costs associated with these flows make up the price of the network’s normal functionality. These networks have limited capacities, which cause the marginal cost of a unit of flow across an edge to increase as congestion builds. In order to limit the expense of a network’s normal demand we aim to increase the resilience of the system and specifically the resilience of the arc capacities. Divisions of critical infrastructure have faced difficulties in recent years as inadequate resources have been available for needed upgrades and repairs. Without being able to determine future factors that cause damage both minor and extreme to the networks, officials must decide how to best allocate the limited funds now so that these essential systems can withstand the heavy weight of society’s reliance. We model these resource allocation decisions using a two-stage stochastic program (SP) for the purpose of network protection. Starting with a general form for a basic two-stage SP, we enforce assumptions that specify characteristics key to this type of decision model. The second stage objective—which represents the price of the network’s routine functionality—is nonlinear, as it reflects the increasing marginal cost per unit of additional flow across an arc. After the model has been designed properly to reflect the network protection problem, we are left with a nonconvex, nonlinear, nonseparable risk-neutral program. This research focuses on key reformulation techniques that transform the problematic model into one that is convex, separable, and much more solvable. Our approach focuses on using perspective functions to convexify the feasibility set of the second stage and second order conic constraints to represent nonlinear constraints in a form that better allows the use of computational solvers. Once these methods have been applied to the risk-neutral model we introduce a risk measure into the first stage that allows us to control the balance between an efficient, solvable model and the need to hedge against extreme events. Using Benders cuts that exploit linear separability, we give a decomposition and solution algorithm for the general network model. The innovations included in this formulation are then implemented on a transportation network with given flow demand  more » « less
Award ID(s):
1633608
NSF-PAR ID:
10341179
Author(s) / Creator(s):
Date Published:
Journal Name:
Thesis for Clemson University
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Urban heat exposure is an increasing health risk among urban dwellers. Many cities are considering accommodating active mobility, especially walking and biking, to reduce greenhouse gas emissions. However, promoting active mobility without proper planning and transportation infrastructure to combat extreme heat exposure may cause more heat-related morbidity and mortality, particularly in future with projected climate change. This study estimated the effectiveness of active trip heat exposure mitigation under built environment and travel behavior change. Simulations of the Phoenix metro region's 624,987 active trips were conducted using the activity-based travel model (ABM), mean radiant temperature (T MRT , net human radiation exposure), transportation network, and local climate zones. Two scenarios were designed to reduce traveler exposure: one that focuses on built environment change (making neighborhoods cooler) and the other on travel behavior (switching from shorter travel time but higher exposure routes to longer travel time but cooler routes) change. Travelers experienced T MRT heat exposure ranging from 29°C to 76°C (84°F to 168°F) without environmental or behavioral change. Active trip T MRT exposures were reduced by an average of 1.2–3.7°C when the built environment was changed from a hotter to cooler design. Behavioral changes cooled up to 10 times more trips than changes in built environment changes. The marginal benefit of cooling decreased as the number of cooled corridors transformed increased. When the most traveled 10 km of corridors were cooled, the marginal benefit affected over 1,000 trips/km. However, cooling all corridors results in marginal benefits as low as 1 trip/km. The results reveal that heavily traveled corridors should be prioritized with limited resources, and the best cooling results come from environment and travel behavior change together. The results show how to surgically invest in travel behavior and built environment change to most effectively protect active travelers. 
    more » « less
  2. Abstract

    The negative impact of climate change continues to escalate flood risk. Floods directly and indirectly damage highway systems and disturb the socioeconomic order. In this study, we propose an integrated approach to quantitatively assess how floods impact the functioning of a highway system. The approach has three parts: (1) a multi‐agent simulation model to represent traffic, heterogeneous user demand, and route choice in a highway network; (2) a flood simulator using future runoff scenarios generated from five global climate models, three representative concentration pathways (RCPs), and the CaMa‐Flood model; and (3) an impact analyzer, which superimposes the simulated floods on the highway traffic simulation system, and quantifies the flood impact on a highway system based on car following model. This approach is illustrated with a case study of the Chinese highway network. The results show that (i) for different global climate models, the associated flood damage to a highway system is not linearly correlated with the forcing levels of RCPs, or with future years; (ii) floods in different years have variable impacts on regional connectivity; and (iii) extreme flood impacts can cause huge damages in highway networks; that is, in 2030, the estimated 84.5% of routes between provinces cannot be completed when the highway system is disturbed by a future major flood. These results have critical implications for transport sector policies and can be used to guide highway design and infrastructure protection. The approach can be extended to analyze other networks with spatial vulnerability, and it is an effective quantitative tool for reducing systemic disaster risk.

     
    more » « less
  3. Critical infrastructure networks, including water, power, communication, and transportation, among others, are necessary to society’s functionality. In recent years, the threat of different types of disruptions to such infrastructure networks has become an increasingly important problem to address. Due to existing interdependencies, damage to a small area of one of the networks could have far-reaching effects on the ability to meet demand across the entire system. Common disruption scenarios include, among others, intentional malevolent attacks, natural disasters, and random failures. Similar works have focused on only one type of scenario, but combining a variety of disruptions may lead to more realistic results. Additionally, the concept of social vulnerability, which describes an area’s ability to prepare for and respond to a disruption, must be included. This should promote not only the protection of the most at-risk components but also ensure that socially vulnerable communities are given adequate resources. This work provides a decision making framework to determine the allocation of defensive resources that accounts for all these factors. Accordingly, we propose a multi-objective mathematical model with the objectives of: (i) minimizing the vulnerability of a system of interdependent infrastructure networks, and (ii) minimizing the total cost of the resource allocation strategy. Moreover, to account for uncertainty in the proposed model, this paper incorporates a means to address robustness in finding the most adaptable network protection plan to reduce the vulnerability of the system of interdependent networks to a variety of disruption scenarios. The proposed work is illustrated with an application to social vulnerability and interdependent power, gas, and water networks in Shelby County, Tennessee. 
    more » « less
  4. In this work, we propose to utilize discrete graph Ricci flow to alter network entropy through feedback control. Given such feedback input can “reverse” entropic changes, we adapt the moniker of Maxwell’s Demon to motivate our approach. In particular, it has been recently shown that Ricci curvature from geometry is intrinsically connected to Boltzmann entropy as well as functional robustness of networks or the ability to maintain functionality in the presence of random fluctuations. From this, the discrete Ricci flow provides a natural avenue to “rewire” a particular network’s underlying geometry to improve throughout and resilience. Due to the real-world setting for which one may be interested in imposing nonlinear constraints amongst particular agents to understand the network dynamic evolution, controlling discrete Ricci flow may be necessary (e.g., we may seek to understand the entropic dynamics and curvature “flow” between two networks as opposed to solely curvature shrinkage). In turn, this can be formulated as a natural control problem for which we employ feedback control towards discrete Ricci-based flow and show that under certain discretization, namely Ollivier-Ricci curvature, one can show stability via Lyapunov analysis. We conclude with preliminary results with remarks on potential applications that will be a subject of future work. 
    more » « less
  5. ABSTRACT

    The presented methodology results in an optimal portfolio of resilience‐oriented resource allocation under weather‐related risks. The pre‐event mitigations improve the capacity of the transportation system to absorb shocks from future natural hazards, contributing to risk reduction. The post‐event recovery planning results in enhancing the system's ability to bounce back rapidly, promoting network resilience. Considering the complex nature of the problem due to uncertainty of hazards, and the impact of the pre‐event decisions on post‐event planning, this study formulates a nonlinear two‐stage stochastic programming (NTSSP) model, with the objective of minimizing the direct construction investment and indirect costs in both pre‐event mitigation and post‐event recovery stages. In the model, the first stage prioritizes a bridge group that will be retrofitted or repaired to improve the system's robustness and redundancy. The second stage elaborates the uncertain occurrence of a type of natural hazard with any potential intensity at any possible network location. The damaged state of the network is dependent on decisions made on first‐stage mitigation efforts. While there has been research addressing the optimization of pre‐event or post‐event efforts, the number of studies addressing two stages in the same framework is limited. Even such studies are limited in their application due to the consideration of small networks with a limited number of assets. The NTSSP model addresses this gap and builds a large‐scale data‐driven simulation environment. To effectively solve the NTSSP model, a hybrid heuristic method of evolution strategy with high‐performance parallel computing is applied, through which the evolutionary process is accelerated, and the computing time is reduced as a result. The NTSSP model is implemented in a test‐bed transportation network in Iowa under flood hazards. The results show that the NTSSP model balances the economy and efficiency on risk mitigation within the budgetary investment while constantly providing a resilient system during the full two‐stage course.

     
    more » « less