Element substitution algorithm for general two-terminal network reliability analyses

IIE Transactions, March, 2007 by Bethel A. Gebre, Jose E. Ramirez-Marquez

1. Introduction

The problem of obtaining the reliability of networks has been extensively researched during the past decades. Within this area of research, one of the classical network reliability problems is known as the 2-Terminal Reliability (2TR) problem. In 2TR analyses, it is of interest to calculate the reliability associated with the existence of connecting paths between two specific network nodes, usually called the source and the sink. That is, in more general terms, one is interested in obtaining the probability that the source and the sink can communicate. There are many operational networks that follow the two-terminal rationale, for example: hard-wired and wireless telecommunications, computer networks, electric power distribution, and circuits within electronic devices, to name just a few. For these networked systems, reliability occupies an important role since it can be used as a tool to assess performance, to make maintenance decisions, and to prioritize system improvements (Ramirez-Marquez and Coit, 2005a) during both the development and the operational phases of the network.

For the 2TR problem, exact computational techniques can be classified into one of the following categories: (i) state enumeration; (ii) network decomposition; (iii) fault and event trees; and (iv) path and cut set enumeration. For large complex systems the most-efficient reliability analysis methods currently available are based on minimal path set enumeration (Kuo et al., 1999; Fotuhi-Firuzabad et al., 2004). The vast majority of such methods assume that both the network and its components (nodes and arcs) have a binary behavior. That is, the network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning. Similarly, most of these techniques assume that the nodes are perfectly reliable and thus, have to be complemented or transformed with methods that account for node failure (Rueger, 1986; Torrieri, 1994; Netes and Filin, 1996; Ke and Wang, 1997).

For large complex networks that follow the 2TR rationale, there is still a need to develop fast computational techniques that can be implemented no matter what kind of behavior the network and its components display. The aim of this paper is to address this need in that we present a general algorithm to determine the binary minimal cut sets of a network that follows the two-terminal rationale. This algorithm was developed based on the inheritance techniques presented in Ramirez-Marquez et al. (2005) and it can be efficiently implemented to account for arc and node failures. Moreover, the algorithm can be extended using the approaches developed by Lin et al. (1995) and Lin (2002) so as to be able to analyze capacitated and multistate two-terminal networks.

The general algorithm presented in this paper was developed as a holistic technique that relies on two subalgorithms that when joined provide fast computation of the minimal cut sets for complex networks. These subalgorithms are based on an inheritance function approach that iteratively generates network cut sets from a specified set, called the "parent/primary" set, that is continuously updated. This inheritance approach was used by Ramirez-Marquez et al. (2005) to develop multistate minimal path vectors, which are the equivalent of minimal path sets for multi-state networks. The general rationale behind the subalgorithms is that elements in the current "parent/primary" set can be substituted by their preceding or succeeding elements thus generating new potential minimal cut sets. Both of these subalgorithms are intuitive and output minimal cut sets thereby reducing the computational time spent on filtering non-minimal cuts. Finally, it should be noted that both of these subalgorithms can independently generate all the minimal cut sets for complex networks. However, when the subalgorithms are implemented together to develop a general algorithm the computational effort to generate the minimal cut sets in complex networks is significantly reduced.

The remainder of the paper is organized as follows. Section 2 provides a problem description, definitions, notations, and assumptions. Section 3 describes existing cut-and-path-based algorithms for binary 2TR problems. Section 4 introduces and discuses the general minimal cut set algorithm developed as part of this research. This section also presents an illustrative step-by-step example on how the algorithms are implemented and elaborates on the implementation of the algorithm in more general 2TR analyses. Section 5 presents computational results obtained from analyzing literature case networks (Kuo et al., 1999; Soh and Rai, 2005) with the proposed algorithm while Section 6 provides future work and conclusions.

2. Problem description, definitions, notation, and assumptions

2.1. Problem description

Let G = (N, A) represent a stochastic directed network with known source node s and sink node t. N = {[n.sub.j]|1 [less than or equal to] j [less than or equal to] 1} represents the set of nodes and A = {[a.sub.h]|1 [less than or equal to] h [less than or equal to] m} represents the set of arcs. The probability associated with network component k working, k = 1,..., l m is represented by [p.sub.k]. The system state vector x = ([x.sub.1], [x.sub.2],..., [x.sub.m]) denotes the state of all the arcs of the network. Function [phi], maps the system state vector into a system state. That is, [phi](x) defines the state of the network connectivity between s and t under system state vector x. 2TR denotes the probability that nodes s and t can communicate through the network components: 2TR is equal to P{[phi](x) = 1}.