Multi-distribution multi-commodity multistate flow network model and its reliability evaluation algorithm

摘要

Multi-state flow networks (MFNs), which allow components to have various states and satisfy the flow conservation law, are widely used to model current real-life networks. The multi-commodity MFN (MMFN) is an extension of the MFN that considers more than one commodity (e.g., material, media, resources, products, and items) in the MFN. Network reliability is an important tool for the evaluation of the performance of various networks. The applications and studies of MMFNs are now more important than ever before. However, to date, only one MMFN has been developed, namely the weighted MMFN (WMMFN). In each component of the WMMFN, all commodities share the same state distribution (the states and their occurrence probabilities); the flows of different commodities are simply summed up for the calculation of the WMMFN reliability. Thus, in this study, a novel multi-distribution MMFN (MMMFN) is proposed that allows each commodity to have its own state distribution on components to complement the WMMFN. A new path-based algorithm is presented for the calculation of the proposed novel MMMFN reliability. The correctness and time complexity of the proposed path-based algorithm will be analyzed and proven. Numerical cases are adopted to demonstrate the proposed MMMFN and the proposed algorithm.