Narrow Results

Certain capacity degradation levels increase travel times on road networks, while traffic demand remains met. Resilience of a road network is higher, if it can take-in higher levels of degradation without leaving any part of the demand unmet. It is important for planners to quantify this, and it can be obtained as the output of an optimization problem. The resultant measure of resilience is demand-specific. To generalize the resilience measure, its sensitivity to change in demand should be studied. We observe that irrespective of the difference in network size or network topology, resilience decreases with increase in demand. We perform computational experiments on different network topologies to investigate the relationship between network resilience and traffic demand. Based on this, we introduce the area under the demand-resilience curve as a generalized index of resilience (GIR). We compare the GIR with traditional network indicators and find that it is in certain ways, better.

Network operation may require that a specified number k of nodes be able to communicate via paths consisting of operating edges and nodes. In an environment of node and edge failure, this leads to associated reliability measures. When the k nodes are known in advance, this has been widely studied as k-terminal reliability; when the k nodes are chosen uniformly at random, this has been studied as k-resilience. A third notion, when it suffices to have anyk nodes communicate, is related to the expected size of the largest component in the network. We generalize these three measures to the probability that given h nodes chosen in advance and i nodes chosen at random, they appear in a component of size at least k = h + i + j. As expected, for general networks, for most choices of (h, i, j) the computation is #P-complete and hence unlikely to admit a polynomial time algorithm. We develop polynomial time algorithms in the special case that the network is series-parallel, which subsume and generalize earlier methods for k-terminal reliability and k-resilience.