Reliability evaluation of a stochastic-flow network in terms of minimal paths with budget constraint

In a stochastic-flow network with budget constraint, the network reliability for level (d, b), i.e., R-(d,R-b), where d is a given demand value and b is a budget limit, is the probability of transmitting at least d units of flow from a source node to a sink node within the budget of b. The problem of evaluating R-(d,R-b) in terms of Minimal Paths (MPs), which is called the (d, b)-MP problem, has been of considerable interest in the recent decades. Here, presenting some new results, an improved algorithm is proposed for this problem. Some numerical comparisons between our MATLAB implementation of the algorithm proposed in this article and a recently proposed one are made. This way, computational comparative results on some benchmarks and thousands of random test problems are provided in the sense of performance profile introduced by Dolan and More. Moreover, complexity results are provided. The complexity and numerical results show the efficiency of our algorithm in comparison with the others. Furthermore, we state how to use the output of the algorithm in order to assess the system reliability. Ultimately, based on the main proposed algorithm, a simple algorithm is stated to evaluate the reliability of some smart grid communication networks.