Study on the multicommodity reliability of a capacitated-flow network

AbstractTraditionally, many researchers solved the multicommodity maximum flow problem by assuming that the arcs of the flow network are deterministic. When the arcs are stochastic (i.e., the capacity of each arc has several values), this article studies how to calculate the probability that a capacitated-flow network with a unique source mode satisfies a demand (d1, d2,…, dp) at the unique sink node, where dk is the demand of commodity k. Such a probability is named the multicommodity reliability and is dependent on capacities of arcs. One solution procedure is proposed to evaluate the multicommodity reliability, which includes two parts: an algorithm to generate all (d1, d2,…, dp)-MPs and a method to calculate the multicommodity reliability in terms of (d1, d2,…, dp)-MPs. Two illustrative examples are given