 Finding all multi-state minimal paths of a multi-state flow network via feasible circulationsYi-Feng Niu, Xiao-Yu Wan, Xiu-Zhen Xu and Dong Ding Reliability Engineering and System Safety, 2020, vol. 204, issue C Abstract: Multi-state minimal paths, called d-minimal paths (d-MPs), are a popular tool for computing the reliability of multi-state flow networks. Most of the existing algorithms seek for d-MPs by solving an NP-hard Diophantine system in terms of the implicit enumeration method that is simple yet inefficient. This paper focuses on the development of a novel method for finding all d-MPs. By exploring the relationship between d-MPs and feasible circulations that are a well-known network flow problem, this paper proposes a distinctive method integrating the traditional max-flow algorithm and a partition technique to find all d-MPs. The developed method seeks for d-MPs by solving feasible circulations, rather than by solving an NP-hard Diophantine system; additionally, it neither requires MPs nor generates duplicate d-MPs during the solution process. Both theoretical and experimental results demonstrate the advantage of the developed method, and a real delivery network example is presented to illustrate its application. Keywords: Reliability; Multi-state flow network; d-minimal paths; Feasible circulation (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:204:y:2020:i:c:s095183202030689x DOI: 10.1016/j.ress.2020.107188 Access Statistics for this article Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares More articles in Reliability Engineering and System Safety from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.