Source-linked AI summary
Modeling s-t Path Availability to Support Disaster Vulnerability Assessment of Network Infrastructure
Timothy C. Matisziw, Alan T. Murray
TL;DR
Network vulnerability assessment must identify facilities whose disruption most threatens source-sink system flow, despite limited planning resources and computationally demanding path-based approaches. The paper proposes an alternative constraint structure that avoids complete s-t path enumeration and applies it to infrastructure planning. In the Ohio application, the PAC formulation achieved 99% savings in solution time and over an 80% reduction in computational effort, while retaining limitations related to path-length thresholds and multiple paths.
Problem
Limited disaster-management budgets require identifying vital facilities, but existing system-flow models rely on complete enumeration of s-t paths and network vulnerability assessment is challenging.
Method
The paper proposes an alternative path-based constraint structure for assessing system-flow survivability after network disruption.
Results
99% savings in solution time and over an 80% reduction in computational effort were achieved by the PAC formulation in the application.
Takeaways & Limitations
The PAC formulation provides computational benefits for infrastructure planning while preserving the formulation’s intended function.
Takeaways & Limitations
The PAC formulation is limited by path-length thresholds and by Zij connections that may involve multiple paths.
Abstract
from arXiv · showhide
The maintenance of system flow is critical for effective network operation. Any type of disruption to network facilities (arcs/nodes) potentially risks loss of service, leaving users without access to important resources. It is therefore an important goal of planners to assess infrastructures for vulnerabilities, identifying those vital nodes/arcs whose debilitation would compromise the most source-sink (s-t) interaction or system flow. Due to the budgetary limitations of disaster management agencies, protection/fortification and planning for the recovery of these vital infrastructure facilities is a logical and efficient proactive approach to reducing worst-case risk of service disruption. Given damage to a network, evaluating the potential for flow between s-t pairs requires assessing the availability of an operational s-t path. Recent models proposed for identifying infrastructure vital to system flow have relied on enumeration of all s-t paths to support this task. This paper proposes an alternative model constraint structure that does not require complete enumeration of s-t paths, providing computational benefits over existing models. To illustrate the model, an application to a practical infrastructure planning problem is presented.
Introduction
Network vulnerability assessment is difficult because disruptions can severely impair service, while limited disaster-planning resources require prioritizing vital facilities. The paper addresses computational challenges by proposing a model for assessing system-flow survivability and illustrating it on Ohio’s interstate highway network.
- Disrupting one or a few critical facilities can severely impair network operability and cause wide-ranging service disruptions.
- Assessing infrastructure vulnerabilities is a planning priority for networks facing intentional or unplanned disruption.
- Limited disaster-management budgets require prioritizing disaster-recovery planning toward facilities most important for network functionality.
- Network complexity and multiple assessment criteria make identifying vital facilities challenging.
- An Ohio interstate highway network application illustrates the benefits of the proposed formulation.
Background
Network vulnerability analysis focuses on how facility disruptions affect s-t connectivity and system flow, while existing path-based formulations face scalability challenges from path enumeration. The paper proposes a path-enumeration-free constraint structure that preserves equivalence while reducing model constraints.
- Vulnerability assessment: Network vulnerability depends on how facility damage affects connectivity, flow, and interactions among source-sink pairs.Facility importance varies with network topology, available alternative facilities, disruption level, and the performance measure considered.
- Vulnerability assessment: The paper models s-t activity as supported when at least one operational s-t path remains available, regardless of that path’s characteristics.The formulation treats interaction between different nodal pairs as independent.
- Existing models: Existing survivability and flow-interdiction models explicitly specify all potential s-t paths and the facilities they contain.Damage to a component removes the associated path; flow is disrupted when no path remains for a pair.
- Existing models: Path enumeration becomes computationally difficult because the number of possible s-t paths can grow exponentially with network size.The number of remaining paths can create difficulties as networks expand.
- Proposed approach: The proposed alternative constraint structure collectively accounts for movement possibilities and establishes an upper bound on worst-case connectivity or flow loss.It requires no a priori identification of all paths and uses fewer constraints while remaining equivalent to fully specified path-based models.
Ohio’s Vital Interstate Infrastructure
The Ohio application evaluates interstate-edge disruptions affecting trucking interactions among metropolitan statistical areas. PAC uses substantially fewer constraints than the path-based formulation, produces equivalent optimal solutions, and requires less computational effort.
- Network and data: The study represents Ohio’s interstate trucking network with 23 vertices, 34 undirected edges, and 15 MSAs interacting through 210 source-sink pairs.Inter-MSA trucking is the network-performance measure, and the model focuses on inter-MSA edges rather than intraregional MSA structure.
- Model size: 59,791 simple s-t paths must be specified a priori for M&K, with path enumeration and redundancy reduction requiring nearly 30 minutes.Each enumerated path becomes a model constraint.
- Results: All 34 problem instances were solved to optimality, and PAC results were identical to M&K results in identifying maximum-disruption edge combinations.The results identify edge sets whose damage maximizes service disruption for each disruption level.
- Results: Four simultaneous edge disruptions could affect over 37% of s-t activity by disconnecting Hamilton, Dayton, Lima, and Toledo from the remaining MSAs.The cutset includes edges on I-80, I-70, I-75, and I-74.
Discussion and Conclusions
The paper presents Path Aggregation Constraints (PAC) as an alternative to complete s-t path enumeration for assessing network-flow vulnerability. PAC reduces computational burden while preserving model intent, supports disaster-planning applications, and has explicit scope limitations.
- Discussion and Conclusions: Network vulnerability assessment identifies facilities whose disruption threatens system flow and supports prioritizing protection, restoration, and response resources.These uses include fortifying vital facilities, prioritizing repairs within a budget, and planning recovery or monitoring strategies.
- Discussion and Conclusions: Path-based vulnerability models can handle multiple sources and sinks and identify vulnerable s-t paths, but complete path specification can become computationally prohibitive.The combinatorial growth of s-t paths is the central computational limitation motivating the alternative formulation.
- Discussion and Conclusions: 99% savings in solution time and over an 80% reduction in computational effort were reported for the Ohio interstate truck-transportation application.The application illustrates computational benefits of the PAC formulation over alternative approaches.
- Discussion and Conclusions: The PAC formulation assumes all network paths are viable for s-t interaction and does not readily track path attributes such as transportation cost or available capacity.Because paths are not explicitly tracked, the formulation is constrained when connectivity depends on more than physical connectivity.
- Discussion and Conclusions: The model addresses worst-case disruptions, while developing an analogous structure for best-case disruption remains an important direction for future work.Best-case disruption corresponds to minimizing system flow loss.