An improved algorithm for the quickest path reliability problem
DOI:
https://doi.org/10.5540/03.2022.009.01.0235Palavras-chave:
Quickest path reliability problem, Minimal paths, Algorithms.Resumo
The quickest path reliability problem (QPRP) emerged for extending the quickest path problem to the system reliability. This problem aims to assess the reliability of a multi-state network (MSN) for transmitting a given d units of a commodity from a source node to a destination node through one single path in the network within T units of time. Most of the proposed algorithms in the literature for this problem need all of the network’s minimal paths as an input. Here, we propose a fast algorithm based on the node-child matrix of the network to address the QPRP that does not need any minimal paths in advance. We discuss the correctness of the algorithm and provide two benchmark examples to illustrate the algorithm and explain its superiority compared to some existing algorithms in the literature.
Downloads
Referências
Yen L Chen and Yeo H Chin. “The quickest path problem”. In: Computers & Operations Research 17.2 (1990), pp. 153–161.
H Salehi Fathabadi and M Forghani-elahabadi. “A note on “A simple approach to search for all d-MCs of a limited-flow network””. In: Reliability Engineering & System Safety 94.11 (2009), pp. 1878–1880.
H Salehi Fathabadi et al. “Determining all minimal paths of a network”. In: Australian Journal of Basic and Applied Sciences 3.4 (2009), pp. 3771–3777. 7
M Forghani-elahabad and N Mahdavi-Amiri. “A simple algorithm to find all minimal path vectors to demand level d in a stochastic-flow network”. In: 5-th Iranian Conference on Applied Mathematics, September 2–4, 2013 Bu-Ali Sina University. 2013.
Majid Forghani-Elahabad. “3 The Disjoint Minimal Paths Reliability Problem”. In: Operations Research. CRC Press, 2022, pp. 35–66.
Majid Forghani-elahabad and Nelson 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.
Majid Forghani-elahabad and Nezam 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.
Majid Forghani-elahabad and Nezam 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.
Majid Forghani-elahabad and Nezam Mahdavi-Amiri. “An efficient algorithm for the multistate two separate minimal paths reliability problem with budget constraint”. In: Reliability Engineering & System Safety 142 (2015), pp. 472–481.
Majid Forghani-Elahabad, Nezam Mahdavi-Amiri, and Nelson 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.
Majid Forghani-elahabad and Wei-Chang Yeh. “An improved algorithm for reliability evaluation of flow networks”. In: Reliability Engineering & System Safety (2022), p. 108371.
Zhifeng Hao et al. “General multi-state rework network and reliability algorithm”. In: Reliability Engineering & System Safety 203 (2020), p. 107048.
Yi-Kuei Lin. “Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network”. In: Computers & Operations Research 30.4 (2003), pp. 567– 575.
Seyed Mehdi 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.
Yi-Feng Niu, Can He, and De-Qiang Fu. “Reliability assessment of a multi-state distribution network under cost and spoilage considerations”. In: Annals of Operations Research (2021), pp. 1–20.
Yi-Feng 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.
Wei-Chang 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.
Wei-Chang Yeh, Wei-Wen Chang, and Chuan-Wei Chiu. “A simple method for the multi-state quickest path flow network reliability problem”. In: 2009 8th International Conference on Reliability, Maintainability and Safety. IEEE. 2009, pp. 108–110.
Wei-Chang 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
