A novel node-based sequential implicit enumeration method for finding all d-MPs in a multistate flow network
The multistate flow network (MFN) has been extensively adapted to model many real-world multi-state systems, which satisfy the flow conservation law, e.g., energy distribution networks, fluid distribution networks, and supply chain networks. Reliability is the key aspect to measure the performance of an MFN. The d-MP (minimal path with capacity level d) is a special vector such that the flow from the source node to the sink node is equal to d, and each arc is saturated in the MFN constructed by this vector. Searching for all d-MPs is the most important methodology in determining the MFN reliability. Until now, the implicit enumeration method (IEM) has been the only way to search for d-MPs. In this study, a novel node-based sequential implicit enumeration method (NSIEM) is proposed to search for all d-MPs in a more efficient way. The truth and the time complexity of the proposed NSIEM is confirmed and investigated. Furthermore, a series of numerical experiments is implemented to compare the efficiency of the NSIEM and the traditional IEM.
implicit enumeration method d-mp multi-state flow network network reliability