A Sequential Decomposition Method for Estimating Flow in a Multi-Commodity, Multistate Network

摘要

The weighted multi-commodity multistate unreliable network (WMMUN) is an extension of the multistate network. It is a new network composed of multistate unreliable components (such as arcs and nodes) with various weight capacities which is able to transmit different types of commodities. Currently, the method used to calculate the direct WMMUN reliability is derived from algorithms based on $D$-minimal path ($D$-MP). The best-known method may fail to find real $D$-MPs, and therefore requires more comparison and verification. A very simple algorithm based on the sequential decomposition method has been developed for finding all real $D$-MPs before calculating the WMMUN reliability. The relationships among the different versions of WMMUN reliability problems have also been clarified. The correctness and computational complexity of the proposed algorithm will be analysed and proven in this paper. An example will be given to illustrate how the WMMUN reliability is evaluated using the proposed algorithm. Computational results compare favorably with existing methods in terms of the running time, the number of $d$-MPs, and the number of $D$-MP candidates.