Game Theory Approach to Transportation Network Vulnerability Measurement

The vulnerability of a transportation network is strongly correlated with the ability of the network to withstand shocks and disruptions. A robust network with strategic redundancy allows for the redistribution or reassignment of traffic without unduly compromising system performance. As such, high-volume edges with limited alternative paths represent system vulnerabilities – a feature of transportation networks that has been exploited in the past to identify critical components. In this thesis, a mixed-strategy, two opponents, non-zero sum, combinatorial game theoretical framework are presented for measuring network vulnerability. Two solution approaches (Shortest Path Algorithm with Entropy function (SPE) & User Equilibrium Assignment with Interest Function (UEI)) are designed to incorporate all origins and destinations in a network in a computationally efficient manner. The presented method differs from previous efforts in that it provides a many-to-many measure of vulnerability and edge-based disruptions that may not reside on a common path. A game considering all possible O-D pairs is constructed between a router, which seeks to maximally ensure safety for all travelers, and a network tester, which seeks to maximize travel cost by disabling edges within the network. Both two approaches adopt this game framework and demonstrated on a small sample network, middle size Sioux Fall, South Dakota network and large scale city network of Anaheim, California. Comparison of two approaches running results on different networks and sensitivity analysis were been discussed. Results indicate rapid solution convergence and good correspondence with a previous method that utilizes criticality function incorporating equilibrium assignment