Utilizing multi-commodity flow formulations to solve network protection problems

Abstract

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT REQUEST OF AUTHOR.] The identification of critical network components is of interest to both interdictors wishing to degrade the network's performance, and to defenders aiming to preserve network performance in the face of disruption. This dissertation focuses on methods for identifying critical subsets of nodes and/or arcs to fortify and/or disable for the purpose of network protection. A common link connecting all studies in this dissertation is our incorporation of the multi-commodity flow formulations into larger multi-level (e.g., minimax) optimization models. ... The last study examines network fortification models that are able to differentiate between failures that are random (e.g., caused by nature) and strategic network failures (e.g., caused by terrorist activities) when performing the allocation of protective resources. This distinction cannot be achieved in the models presented previously in this dissertation. The desired properties of such differentiating formulations are derived by specifying a set of priori assumptions. The criticality indexes in these models, which are necessary to assess the impact of a disruption, are pre-computed through the resolution of the multi-commodity based User Equilibrium (UE) traffic assignment model and applied to urban transportation networks. Novel valid inequalities and linearization techniques are applied to the dual version of the nonlinear UE multi-commodity model to improve its computational efficiency. Computational results demonstrate that the reformulated linear dual model is effective to solve large size instances to near-optimality; and that the optimal allocation of resources as identified by a component-based formulation may potentially be suboptimal when a network is at risk of multiple simultaneous failures for both types of disruptions (i.e., nature- and terrorist-based). We also demonstrate that fortification models for component or scenario-based disruptions can provide different resource allocations for both types of disruptions.