Algorithm to Compute Urban Road Network Resilience

Road network resilience is emerging as a vital planning criterion. Yet, unique and cross-comparable indices for road network resilience are scarce. One of the recent approaches determines resilience as a unique network attribute based on the system travel time at an upper envelope of operable disruptions. This upper envelope represents 'critical states' (or tipping points) of capacity disruptions. Critical state gives a bounding capacity degradation vector, beyond which the network cannot wholly cater to the origin-destination demand even under the best possible traffic assignment. However, solving the critical state identification problem (CSP) on real-scale networks has remained a challenge. This paper presents a weighted fictitious play algorithm to fill this gap. CSP has been previously envisaged as a two-player game between a network attacker and a network defender. Here, we make the players play iteratively, and make them learn from the competitor's past strategies so that they converge to an equilibrium. We illustrate the method on a simple toy network, and solve it on different real-life networks. Resilience of the Anaheim city network was computed in 42.8 min., considerably outperforming-both in problem-size and solution-time-the previous, two-space genetic algorithm.