A simple algorithm for reliability evaluation of stochastic-flow networks under distance limitation
DOI:
https://doi.org/10.5540/03.2023.010.01.0014Keywords:
Multistate flow networks, System reliability, Distance limitation, Minimal pathsAbstract
Various real-world systems, including computer and communication networks, trans- portation, and distribution systems, can be modeled as a stochastic/multistate flow network (MFN). Reliability indices are of great importance in evaluating the quality of service in MFNs. One such index is the two-terminal reliability (2TR), which represents the probability that the maximum flow in the network is not less than a certain demand level. Researchers have investigated the 2TR problem for MFNs, considering constraints such as budget, time, or distance limitations. Nevertheless, distance constraints have received relatively less attention in the literature, despite their significant role in optimizing the efficiency of some transmission networks. Hence, this study focuses on the 2TR problem with a distance constraint in an MFN and proposes a simple yet efficient algorithm to solve it. We demonstrate the effectiveness of our algorithm through a benchmark example.
Downloads
References
R.K Ahuja, T.L Magnanti, and J.B Orlin. Network flows: theory, algorithms and applications. Prentice Hall, 1995.
G. Bai, Z. Tian, and M.J Zuo. “Reliability evaluation of multistate networks: An improved algorithm using state-space decomposition and experimental comparison”. In: IISE Translactions 50.5 (2018), pp. 407–418.
M. Bao et al. “Definitions and reliability evaluation of multi-state systems considering state transition process and its application for gas systems”. In: Reliability Engineering & System Safety 207 (2021), p. 107387.
D. Canca and G. Laporte. “Solving real-size stochastic railway rapid transit network construction scheduling problems”. In: Computers & Operations Research 138 (2022), p. 105600
H. Cancela, M. El Khadiri, and L. A. Petingi. “Polynomial-time topological reductions that preserve the diameter constrained reliability of a communication network”. In: IEEE Transactions on Reliability 60.4 (2011), pp. 845–851.
M. Forghani-Elahabad. “3 The Disjoint Minimal Paths Reliability Problem”. In: Operations Research. CRC Press, 2022, pp. 35–66.
M. Forghani-elahabad. “1 Exact reliability evaluation of multistate flow networks”. In: Systems Reliability Engineering. De Gruyter, 2021, pp. 1–24.
M. Forghani-elahabad and L. H Bonani. “An improved algorithm for RWA problem on sparse multifiber wavelength routed optical networks”. In: Optical switching and networking 25 (2017), pp. 63–70.
M. Forghani-elahabad and L. H. Bonani. “Finding all the lower boundary points in a multi-state two-terminal network”. In: IEEE Transactions on Reliability 66.3 (2017), pp. 677–688.
M. Forghani-elahabad and E. Francesquini. “An Improved Vectorization Algorithm to Solve the d-MP Problem”. In: Trends in computational and Applied Mathematics 24.1 (2023), pp. 19–34.
M. Forghani-elahabad and N. Kagan. “Assessing reliability of multistate flow networks under cost constraint in terms of minimal cuts”. In: International Journal of Reliability, Quality and Safety Engineering 26.05 (2019), p. 1950025.
M. Forghani-elahabad and N. Kagan. “Reliability evaluation of a stochastic-flow network in terms of minimal paths with budget constraint”. In: IISE Transactions 51.5 (2019), pp. 547–558.
M. Forghani-elahabad, N. Kagan, and N. Mahdavi-Amiri. “An MP-based approximation algorithm on reliability evaluation of multistate flow networks”. In: Reliability Engineering & System Safety 191 (2019), p. 106566.
M. Forghani-elahabad and N. Mahdavi-Amiri. “A New Algorithm for Generating All Minimal Vectors for the q SMPs Reliability Problem With Time and Budget Constraints”. In: IEEE Transactions on Reliability 65.2 (2015), pp. 828–842.
M. Forghani-elahabad and N. Mahdavi-Amiri. “A new efficient approach to search for all multi-state minimal cuts”. In: IEEE Transactions on Reliability 63.1 (2014), pp. 154–166.
M. Forghani-elahabad and N. Mahdavi-Amiri. “An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint”. In: Reliability Engineering & System Safety 142 (2015), pp. 472–481.
M. Forghani-elahabad and N. Mahdavi-Amiri. “On Search for all d-MCs in a Network Flow”. In: Iranian Journal of Operations Research 4.2 (2013), pp. 108–126.
M. Forghani-Elahabad, N. Mahdavi-Amiri, and N. Kagan. “On multi-state two separate minimal paths reliability problem with time and budget constraints”. In: International Journal of Operational Research 37.4 (2020), pp. 479–490.
M. Forghani-elahabad and W. C. Yeh. “An improved algorithm for reliability evaluation of flow networks”. In: Reliability Engineering & System Safety 221 (2022), p. 108371.
Z. Hao et al. “General multi-state rework network and reliability algorithm”. In: Reliability Engineering & System Safety 203 (2020), p. 107048.
J. S. Lin, C. C. Jane, and J. Yuan. “On reliability evaluation of a capacitated-flow network in terms of minimal pathsets”. In: Networks 25.3 (1995), pp. 131–138.
S. M. Mansourzadeh et al. “A Comparative Study of Different Approaches for Finding the Upper Boundary Points in Stochastic-Flow Networks”. In: International Journal of Enterprise Information Systems (IJEIS) 10.3 (2014), pp. 13–23.
M. A. S. Monfared, M. Rezazadeh, and Z. Alipour. “Road networks reliability estimations and optimizations: A Bi-directional bottom-up, top-down approach”. In: Reliability Engineering & System Safety 222 (2022), p. 108427.
F. Nazarizadeh et al. “An analytical model for reliability assessment of the rail system considering dependent failures (case study of Iranian railway)”. In: Reliability Engineering & System Safety 227 (2022), p. 108725.
Y. F. Niu, Zi-You G., and W. H. K. Lam. “Evaluating the reliability of a stochastic distribution network in terms of minimal cuts”. In: Transportation Research Part E: Logistics and Transportation Review 100 (2017), pp. 75–97.
Y. F. Niu, C. He, and D. Q. Fu. “Reliability assessment of a multi-state distribution network under cost and spoilage considerations”. In: Annals of Operations Research (2021), pp. 1–20.
Y. F. Niu et al. “Finding all multi-state minimal paths of a multi-state flow network via feasible circulations”. In: Reliability Engineering & System Safety 204 (2020), p. 107188.
T. Xiahou et al. “Reliability modeling of modular k-out-of-n systems with functional dependency: A case study of radar transmitter systems”. In: Reliability Engineering & System Safety 233 (2023), p. 109120.
B. Xu et al. “A multistate network approach for reliability evaluation of unmanned swarms Safety 219 (2022), p. 108221.
C. T. Yeh et al. “Rail transport network reliability with train arrival delay: A reference indicator for a travel agency in tour planning”. In: Expert Systems with Applications 189 (2022), p. 116107.
W. C. Yeh. “A fast algorithm for quickest path reliability evaluations in multi-state flow networks”. In: IEEE Transactions on Reliability 64.4 (2015), pp. 1175–1184.
W. C. Yeh. “A novel method for the network reliability in terms of capacitated-minimum-paths without knowing minimum-paths in advance”. In: Journal of the Operational Research Society 56.10 (2005), pp. 1235–1240.
W. C. Yeh et al. “Application of LSTM based on the BAT-MCS for binary-state network approximated time-dependent reliability problems”. In: Reliability Engineering & System Safety (2022), p. 108954.
W. C. Yeh et al. “New binary-addition tree algorithm for the all-multiterminal binary-state network reliability problem”. In: Reliability Engineering & System Safety 224 (2022), p. 108557.
W. C. Yeh et al. “Novel binary-addition tree algorithm for reliability evaluation of acyclic multistate information networks”. In: Reliability Engineering & System Safety 210 (2021), p. 107427.
Z. Zhang and F. Shao. “A diameter-constrained approximation algorithm of multistate two-terminal reliability”. In: IEEE Transactions on Reliability 67.3 (2018), pp. 1249–1260.
