A network reliability algorithm for a stochastic flow network with non-conservation flow

Network reliability is defined as the probability that at least demand d can be sent successfully through a system with multistate arcs. Some existing algorithms based on minimal paths (MPs) have been developed to extract all d-MPs for network reliability evaluation under the assumption of the conservation flow law. All the d-MPs are necessary capacity vectors for d. However, non-conservation flow cases, including decrease and increase flows, exist in real systems. Thus, an algorithm for generating all the d-MPs in non-conservation flow cases is required for network reliability evaluation. Such the d-MPs are renamed d-MPncs as follows. In this study, the change rates of all the arcs are defined to represent the changes in the flow. A recursive algorithm is developed to generate all feasible flow vectors satisfying at least d with the integer-type flow to represent undivided demands. Consumed-capacity vectors with respect to all the MPs are formulated to calculate the exact consumed capacity for all arcs and to obtain capacity vectors as d-MPnc candidates. Finally, a cyclic check and comparison approach are performed to search for all the d-MPncs. A numerical example, time complexity, and efficiency investigation are presented to demonstrate the feasibility of the proposed algorithm.