An optimization approach for deriving upper and lower bounds of transportation network vulnerability under simultaneous disruptions of multiple links

Abstract

This paper aims to develop an optimization approach for deriving the upper and lower bounds of transportation network vulnerability under simultaneous disruptions of multiple links without the need to evaluate all possible combinations as in the enumerative approach. Mathematically, we formulate the upper and lower bounds of network vulnerability as a binary integer bi-level program (BLP). The upper-level subprogram maximizes or minimizes the remaining network throughput under a given number of disrupted links, which corresponds to the upper and lower vulnerability bounds. The lower-level subprogram checks the connectivity of each origin-destination (O-D) pair under a network disruption scenario without path enumeration. Two alternative modeling approaches are provided for the lower-level subprogram: the virtual link capacity-based maximum flow problem formulation and the virtual link cost-based shortest path problem formulation. Computationally, the BLP model can be equivalently reformulated as a single-level mixed integer linear program by making use of the optimality conditions of the lower-level subprograms and linearization techniques for the complementarity conditions and bilinear terms. Numerical examples are also provided to systematically demonstrate the validity, capability, and flexibility of the proposed optimization model. The vulnerability envelope constructed by the upper and lower bounds is able to effectively consider all possible combinations without the need to perform a full network scan, thus avoiding the combinatorial complexity of enumerating multi-disruption scenarios. Using the vulnerability envelope as a network performance assessment tool, planners and managers can more cost-effectively plan for system protection against disruptions, and prioritize system improvements to minimize disruption risks with limited resources.