A new hybrid inequality BAT for comprehensive all-level d-MP identification using minimal paths in Multistate Flow Network reliability analysis

In various network applications like wireless sensors, utilities, IoT, and transport systems, multistate flow networks (MFNs) serve as valuable models. A d-level minimal path (d-MP) is a unique type of MFN characterized by having a maximum flow of d without any redundant arcs. Assessing MFN reliability is critical and often relies on the d-MP algorithm, a foundational method for calculating reliability. Existing d-MP algorithms, however, lack the capability to concurrently identify all-level d-MPs. We propose a novel algorithm, the Hybrid Inequality Binary-Addition-Tree (IBAT), which overcomes existing limitations by concurrently discovering all-level d-MPs (decision-making points), thus enabling more informed decision-making. This hybrid IBAT combines the IBAT with several key techniques: the path-based layered-search algorithm (PLSA), sequential verification, the MP-to-arc state transformation, the cycle test, and the logarithmic prime pairwise comparison method (LPM). In contrast to existing methods, our BAT-based approach consistently showcases superior performance in the parallelized retrieval of all-level d-MPs, as substantiated through experiments conducted on 12 benchmark MFNs. Compared to existing methods, our BAT-based approach demonstrates superior performance in parallelized retrieval of all-level d-MPs in the execution times in discovering d-MPs across all levels, as validated by experiments on 12 benchmark MFNs.