An efficient method for evaluating network-reliability with variable link-capacities

An efficient method is proposed to evaluate the network reliability with variable link capacities when the simple paths of the network are known. Most of the evaluation techniques proposed in the literature so far are based on enumerating the k-composite paths, each of which is a union of k simple paths. Although some of those methods lead to correct results, the redundancy is still quite large and may occur repeatedly each time the higher order composite paths are generated. This paper proposes a new method based on the concepts of additivity and eligibility properties defined in the text. The authors identify a composite path as a subnetwork which in general contains more simple paths than those involved in composition, and add only a minimal set of links at each step which gives maximal increase on the maximum capacity flow of the subnetwork. Thereby, they reduce the possible occurrence of redundancy significantly. The number of composite paths considered for the capacity computation is also greatly reduced. Furthermore, it is not necessary to keep the information on how many and which simple paths have been used in each composite path. Some numerical examples illustrate the efficiency of the method