Determination and utilization of minimal upper paths for reliability analysis of planar flow networks

Abstract

A stocastic flow network is a useful structure for representing various transmission systems(e.g., power transmission, pipeline, traffic, communication systems) in which the flow capacity of each element can be described by a random variable. An important performance measure for such systems is the so called ``flow network reliability`` which is defined as the probability that a required amount of flow can be transmitted from a source to a terminal. The minimal upper vector approach is an exact and general method for calculating the flow network reliability of a network with discrete random element capacities. It consists of two steps, namely, determination of minimal upper vectors(or minimal upper paths for a binary-state network) and calculation of the desired reliability. Although extensive research has been conducted for the second step, little work has been concerned with developing efficient methods for the first. This thesis develops an algorithm for determining the minimal upper paths of a binary-state planar flow network. The proposed method constructs a tree of subnetworks generated by combining minimal paths, and eliminates unnecessary subnetworks from the tree based upon our elimination criteria developed. Computational results indicate that the criteria are effective in reducing the number of explicitly considered subnetworks, and thereby, in reducing the amount of computational effort required. The minimal upper vectors can be used to identify the most reliable path for sending a required amount of flow from a source to a terminal in a stochastic flow network. An algorithm for determining the most reliable path of a binary-state planar flow network is also developed in this thesis. The proposed method constructs a tree of subnetworks ina similar way as in determining minimal upper paths. Additional criteria are developed to leiminate unnecessary subnetworks from the enumeration tree. Computational results indicate that the elimination criteria are...