Measuring network reliability considering paradoxes: multiple network demon approach

Abstract

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 OD-specific demon that seeks the opposite by damaging links in the network. This problem assumes the presence of only one demon in each OD pair and assumes the capacity reduction to be 50% if the link is selected for damage by one or more OD-specific demons. The game is typically expressed as a path-based formulation, which is computationally intensive since the formulation requires path enumeration. In this paper we relax the assumptions on the OD-specific nature of the demons and the capacity reduction and propose a link-based multiple network demon formulation via the nonlinear complementarity problem approach where each demon is free to select any link to damage. Under this framework, we examine the effects of the proposed model on total expected network cost and reliability measures, as well as demonstrate through specific examples paradoxical phenomena that if one adds a road to a network then all travelers may be worse off in terms of total expected network cost and/or travel time reliability. Overall the results indicate the importance of the 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.