Measuring Network Reliability by considering Paradoxes: Multiple Network Demon Approach

Traditionally, game theoretic approaches to measuring transport network reliability have relied on the outcome of a game played between network users seeking to minimize their travel costs and an origin-destination-specific (O-D-specific) demon that seeks the opposite by damaging links in the network. This problem assumes the presence of only one demon in each O-D pair and assumes the capacity reduction to be 50% if the link is selected for damage by one or more O-D-specific demons. The game is typically expressed as a path-based formulation, which is computationally intensive since the formulation requires path enumeration. With relaxation of the assumptions on the O-D-specific nature of the demons and the capacity reduction, a link-based multiple network demon formulation is proposed by the nonlinear complementarity problem approach, in which each demon is free to select any link to damage. Within this framework, the effects of the proposed model on total expected network cost and reliability measures are examined, and specific examples demonstrate the paradoxical phenomenon that if one adds a road to a network, then all travelers may be worse off for total expected network cost or travel time reliability. Overall, the results indicate the importance of assumptions used to total expected network cost and reliability measures and provide some insights into the problem of ignoring these paradoxical phenomena in reliable and robust network design.