AN ALGORITHM FOR RELIABILITY EVALUATION OF PROBABILISTIC MULTICOMMODITY FLOW NETWORKS WITH BUDGET CONSTRAINTS

摘要

Many real-world systems such as transportation systems, logistics/distribution systems, and manufacturing systems can be regarded as multicommodity flow networks whose arcs have independent, finite and multi-valued random capacities. Such a flow network is a multistate system with multistate components and its reliability for level (d;c), i.e., the probability that k different types of commodity can be transmitted from the source node to the sink node in the way that the demand level d=(d_1,d_2,...,d_k) is satisfied and the total transmission cost is less than or equal to c, can be computed in terms of minimal path vectors to level (d;c) (named (d;c)-MPs here). The main objective of this paper is to present a simple algorithm first to generate all (d;c)-MPs of such a system and then to calculate its reliability in terms of such (d;c)-MPs by further applying the state-space decomposition method. An example is given to illustrate the proposed method.