Determination of minimal upper paths is an important step in calculating the reliability (i.e. the probability that a required amount of flow can be transmitted from a source to a terminal) of stochastic flow networks. This paper presents an algorithm for determining minimal upper paths of a planar flow network. Four criteria are developed to eliminate unnecessary subnetworks from the enumeration tree. Computational results indicate that the developed criteria are effective in reducing the number of explicitly considered subnetworks, and thereby, in reducing the amount of computational effort required. Minimal upper paths can be also utilized to calculate certain component importance measures or to identify the most reliable path for sending a required amount of flow from a source to a terminal.
1 Introduction
A stochastic flow network is a useful structure for representing various physical 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 flow network reliability can be evaluated in several ways) -4 Among them, we consider an approach which consists of three steps, 3 namely, determination of minimal paths, identification of minimal upper paths (or valid groups3), and calculation of the desired reliability. Techniques for the first and third steps are well known (e.g. see Berge, 5 Misra and Misra, 6 and Jasmon and Kai 7 for the first and Abraham, 8 Locks, 9 and Aven ~Β° for the third step). However, relatively little work has been concerned with determining minimal upper paths, i.e. minimal network topologies which can transmit a required amount of flow from a source to a terminal for a given network.
This paper presents a method for determining minimal upper paths assuming that the flow network is * To whom correspondence should be addressed.