Partition-based algorithm for estimating transportation network reliability with dependent link failures

Journal of Advanced Transportation, Fall, 2008 by Agachai Sumalee, David P. Watling

Evaluating the reliability of a transportation network often involves an intensive simulation exercise to randomly generate and evaluate different possible network states. This paper proposes an algorithm to approximate the network reliability which minimizes the use of such simulation procedure. The algorithm will dissect and classify the network states into reliable, unreliable, and un-determined partitions. By postulating the monotone property of the reliability function, each reliable and/or unreliable state can be used to determine a number of other reliable and/or unreliable states without evaluating all of them with an equilibrium assignment procedure. The paper also proposes the cause-based failure framework for representing dependent link degradation probabilities. The algorithm and framework proposed are tested with a medium size test network to illustrate the performance of the algorithm.

1. Introduction

In system engineering, reliability may be defined as the degree of stability of the quality of service that a system normally offers (Bell and Iida 1997). The degree of stability of a transport network can be interpreted as the ability of the network to meet expected goals measured by some indicators under different circumstances (e.g. variability in flows and physical network capacities). A range of different indicators have been proposed depending on the features of variability modeled and the objectives of the analysis. These indicators include connectivity reliability (Asakura et al. 2003), network vulnerability (Berdica 2002; Taylor et al. 2006), capacity reliability (Chen et al. 2002; Sumalee and Kurauchi 2006), travel time reliability (Asakura 1999; Du and Nicholson 1997), total travel time reliability (Clark and Watling 2005; Sumalee et al. 2007), and demand satisfaction (Heydecker et al. 2007). In the present paper, we shall specifically focus on problems in which link capacities are variable (stochastic), and where the aim is to compute a travel time reliability index.

The initial impetus for research in the area of stochastic capacity reliability analysis arose from the study of major natural events, such as earthquakes, affecting the 'connectivity' of the network (Bell and Iida 1997). The objective of connectivity reliability analysis is then to compute the probability that an origin-destination movement will be connected by at least one path consisting of all 'open' links. Travel time reliability analysis extends the concept of connectivity analysis. While connectivity is concerned with the probability of any path being available, however long the travel time, travel time reliability is concerned with the probability of availability of a path with an acceptable travel time.

A common theme to most approaches in this area is the assumption of statistical independence between links in the degradation model. For the study of transport networks, the degradation of different links may often have common underlying causes (e.g. flood, snowfall or earthquake). In such cases, assuming independence tends to provide an over-optimistic estimate of performance. On the other hand, the assumption of dependent link failure probabilities may impose more complexities and hence require more computational efforts. The paper proposes the cause-based framework (as described in the next Section) in which different causes of failures are defined (e.g. flood or earthquake). Under each cause, the independent link degradation probabilities can be defined separately. Despite the independence of link degradation under each cause of failure (so-called conditional independence), the causal tree structure gives rise to an implicit specification of correlated (dependent) link degradations.

The computation of the reliability measure is also a major challenge, especially if realistic correlation and user-behavior models are to be adopted. To tackle this issue, early developments have adopted Monte Carlo simulation (MC) to generate supply and/or demand uncertainties for the equilibrium-based traffic model. Du and Nicholson (1997) simulated the network capacity degradation level using MC to establish the lower and upper bounds of the network reliability indicator. Similarly, Chen et al (2002) and Sumalee and Kurauchi (2006) adopted MC to evaluate network capacity reliability. The flexibility of MC comes with the trade-off of a potentially high computational burden.

Based on these observations, Sumalee and Watling (2003) proposed a method for estimating travel time reliability under dependent link failures, which operates by identifying those network states with large probabilities in order to reduce the total number of considered network states. However, this approach will be efficient only if some scenarios have high probabilities (and others are trivial states). The present paper proposes a different approach to avoid this pitfall by dissecting the network states into a number of reliable, unreliable, and un-determined partitions. The paper postulates an important monotone property of the reliability function, which will be clarified later in Section 3.2. This assumption will allow us to determine a number of reliable and unreliable partitions by evaluating only a few network states with a network assignment model. Some undefined partitions will remain after applying this algorithm in which the stratified MC (as described in Section 3.4) will be applied to evaluate their associated reliability probabilities.