×
Lin, Yi-Kuei; Chen, Shin-Guang

An efficient searching method for minimal path vectors in multi-state networks. (English) Zbl 1490.90105

Ann. Oper. Res. 312, No. 1, 333-344 (2022).
Summary: Searching for minimal path vectors (MPVs) is an important topic in solving network related problems, especially for the evaluation of network reliability. One of the popular approaches, namely the three-stage method (TSM), is influenced deeply on the efficiency of searching for minimal path vectors in multi-state networks (MSN). TSM consists of three stages, i.e., searching for all minimal path sets, searching for all MPVs, and calculating union probability on MPVs. After reviewing previous works in the literaure, this paper proposes a more efficient method based on cyclic check on the candidates of MPVs, which can do an efficient searching for MPVs in MSNs and even reduce the three-step approach to two-step approach. Benchmarking with the well-known algorithms are made in this paper, and more complicated networks are also examined for verification of the proposed method.

Cited in 2 Documents

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
90B15 Stochastic network models in operations research

Keywords:

network reliability; minimal path sets; minimal path vectors; fast enumeration; cyclic check
Cite Review PDF
Full Text: DOI

References:

[1] Aggarwal, KK; Gupta, JS; Misra, KB, A simple method for reliability evaluation of a communication system, IEEE Transactions on Communications, 23, 563-565 (1975) · Zbl 0349.94003 · doi:10.1109/TCOM.1975.1092838
[2] Chen, S. G. (2013). Efficiency improvement in explicit enumeration for integer programming problems. In 2013 IEEE international conference on industrial engineering and engineering management, Bangkok, Thailand (pp 98-100).
[3] Chen, S. G. (2014a). Reduced recursive inclusion-exclusion principle for the probability of union events. In 2014 IEEE international conference on industrial engineering and engineering management (pp. 1-3). Selangor, Malaysia.
[4] Chen, S. G. (2014b). Reduced recursive sum of disjoint product in network reliability. In 2014 the 20th ISSAT international conference on reliability and quality in design (pp. 170-173). Seattle, Washington, USA.
[5] Chen, S. G. (2016). Optimal re-arrangement in fast enumeration for integer programming problems. In 2016 IEEE international conference on industrial engineering and engineering management, (pp 1255-1258).
[6] Chen, SG; Lin, YK, Search for all minimal paths in a general large flow network, IEEE Transactions on Reliability, 61, 4, 949-956 (2012) · doi:10.1109/TR.2012.2220897
[7] Chen, SG; Lin, YK, Searching for \(d\)-MPs with fast enumeration, Journal of Computational Science, 17, 139-147 (2016) · doi:10.1016/j.jocs.2016.05.011
[8] Colbourn, CJ, The combinatorics of network reliability (1987), Oxford: Oxford University Press, Oxford
[9] Ford, LR; Fulkerson, DR, Flows in networks (1962), Princeton: Princeton University Press, Princeton · Zbl 0106.34802
[10] Lee, SH, Reliability evaluation of a flow network, IEEE Transactions on Reliability, 29, 24-26 (1980) · Zbl 0428.90024 · doi:10.1109/TR.1980.5220695
[11] Lin, JS; Jane, CC; Yuan, J., On reliability evaluation of a capacitated-flow network in terms of minimal pathsets, Networks, 25, 131-138 (1995) · Zbl 0828.90038 · doi:10.1002/net.3230250306
[12] Lin, YK, A simple algorithm for reliability evaluation of a stochastic-flow network with node failure, Computers and Operations Research, 28, 13, 1277-1285 (2001) · Zbl 0989.90015 · doi:10.1016/S0305-0548(00)00039-3
[13] Lin, YK; Chen, SG, A maximal flow method to search for \(d\)-MPs in stochastic-flow networks, Journal of Computational Science, 22, 119-125 (2017) · doi:10.1016/j.jocs.2017.09.009
[14] Lin, YK; Chen, SG, A merge search approach to find minimal path vectors in multistate networks, International Journal of Reliability, Quality and Safety Engineering, 24, 1, 1750005-1-1750005-12 (2017) · doi:10.1142/S021853931750005X
[15] Ramirez-Marquez, JE; Gebre, BA, A classification tree based approach for the development of minimal cut and path vectors of a capacitated network, IEEE Transaction on Reliability, 56, 3, 474-487 (2007) · doi:10.1109/TR.2007.902788
[16] Rebaiaia, M. L., Ait-Kadi, D. (2012). An efficient algorithm for enumerating minimal pathsets in communication networks. In 4th international conference on networked digital technologies, Springer, Berlin, Dubai, UAE, communications in computer and information science, (Vol. 293, pp. 444-458)
[17] Xue, J., On multistate system analysis, IEEE Transactions on Reliability, 34, 4, 329-337 (1985)
[18] Yeh, WC, A simple algorithm to search for all \(d\)-MPs with unreliable nodes, Reliability Engineering and System Safety, 73, 49-54 (2001) · doi:10.1016/S0951-8320(01)00032-1
[19] Yeh, WC, A simple method to verify all \(d\)-minimal path candidates of a limited-flow network and its reliability, The International Journal of Advanced Manufacturing Technology, 20, 1, 77-81 (2002) · doi:10.1007/s001700200127
[20] Zuo, MJ; Tian, Z.; Huang, HZ, An efficient method for reliability evaluation of multistate networks given all minimal path vectors, IIE Transactions, 39, 811-817 (2007) · doi:10.1080/07408170601013653
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.