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

Abstract

In a stochastic-flow network with budget constraint, the network reliability for level (d, b), i.e., $R_{(d,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,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 Moré. 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.

Keywords:

• Reliability
• stochastic-flow networks
• budget constraint
• (d
• b)-MP problem

Acknowledgments

The authors are grateful to both the editor and anonymous referees for their constructive comments and recommendations, which have significantly improved the presentation of this paper.

Additional information

Funding

The authors thank FAPESP [Grant 15/21924-1] for supporting this work.

Notes on contributors

Majid Forghani-elahabad

Majid Forghani-elahabad is a postdoctoral researcher at the University of São Paulo (USP). He received his B.Sc. degree in applied mathematics from Yazd University in 2005, his M.S. degree in applied mathematics from University of Tehran in 2008, and his Ph.D. degree in operations research from Sharif University of Technology, in 2014. He was a postdoctoral research position at the Federal University of ABC (UFABC) and lecturer at Sharif University of Technology and several other universities. He has served as a reviewer of several journals such as Reliability Engineering and System Safety, Expert Systems with Applications, and Journal of Natural Gas Science and Engineering. He is currently working on evaluating reliability of communication networks in a smart grid.

Nelson Kagan

Nelson Kagan received the Dipl. Ing. and M.Sc. degrees from the Polytechnic School, University of São Paulo, in 1982 and 1988 respectively and his Ph.D. from the University of London in 1993. He is a Full Professor at Polytechnic School, University of São Paulo where he lectured since 1983. His research interests are related to power system planning, power quality and smart grids. He coordinates the Center of Power Quality and Regulation Studies and the Research Center in Smart Energy Grids at the University of Sao Paulo. His research group has been developing research activities involving most of the Brazilian utilities.