Reliability Evaluation of a Multicommodity Capacitated-Flow Network in Terms of Minimal Pathsets

10.6186/IJIMS.2016.27.3.4

Jsen-Shung Lin

Reliability ； capacitated-flow network ； d-MP

International Journal of Information and Management Sciences

27卷3期（2016 / 09 / 01）

269 - 281

英文

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 = (d_1, d_2, . . . , d_k), 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, can be computed in terms of minimal path vectors to level d (named d-MPs here). The main objective of this paper is to present a simple algorithm to generate all d-MPs of such a flow network for each level d = (d_1, d_2, . . . , d_k) in terms of minimal pathsets. Three examples are given to illustrate how all d-MPs are generated by our algorithm and then the reliability of one example is computed.

1. Aggarwal, K. K.,Gupta, J. S.,Misra, K. G.(1975).A simple method for reliability evaluation of a communication system.IEEE Transactions on Communication,23,563-565.
2. Ahuja, R. K.,Magnanti, T. L.,Orlin, J. B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey.:Prentice-Hall.
3. Aven, T.(1985).Reliability evaluation of multistate systems with multistate components.IEEE Transactions on Reliability,34,473-479.
4. Bai, G.,Tian, Z.,Zuo, M. J.(2016).An improved algorithm for finding all minimal paths in a network.Reliability Engineering and System Safety,150,1-10.
5. Chen, S. G.,Lin, Y. K.(2012).Search for all minimal paths in a general large flow network.IEEE Transactions on Reliability,61,949-956.
6. Doulliez, P.,Jamoulle, J.(1972).Transportation networks with random arc capacities.RAIRO, Recherche Operationnnelle,3,45-60.
7. El-Neweihi, E.,Proschan, F.,Sethuraman, J.(1978).Multistate coherent systems.Journal of Applied Probability,15,675-688.
8. Evans, J. R.(1976).Maximum flow in probabilistic graphs - the discrete case.Networks,6,161-183.
9. Horowitz, E.,Sahni, S.,Rajasekaran, S.(1996).Computer Algorithms/C++.New York:Computer Science Press.
10. Hudson, J. C.,Kapur, K. C.(1985).Reliability bounds for multistate systems with multistate components.Operations Research,33,153-160.
11. Hudson, J. C.,Kapur, K. C.(1983).Reliability analysis for multistate systems with multistate components.IIE Transactions,15,127-135.
12. Jane, C. C.,Laih, Y. W.(2008).A practical algorithm for computing multi-state two-terminal reliability.IEEE Transactions on Reliability,57,295-302.
13. Jane, C. C.,Laih, Y. W.(2010).A dynamic bounding algorithm for approximating multi-state two-terminal reliability.European Journal of Operations Research,205,625-637.
14. Jane, C. C.,Laih, Y. W.(2010).Computing multi-state two-terminal reliability through critical arc states that interrupt demand.IEEE Transactions on Reliability,59,368-345.
15. Lin, J. S.(1998).Reliability evaluation of capacitated-flow network with budget constraints.IIE Transactions,30,1175-1180.
16. Lin, J. S.,Jane, C. C.,Yuan, J.(1995).On reliability evaluation of a capacitated-flow network in terms of minimal pathsets.Networks,25,131-138.
17. Lin, Y. K.(2010).Reliability evaluation for overall-terminal multistate flow networks with bi-directed arcs.Expert Systems with Applications,37,66696674.
18. Niu, Y. F.,Xu, X. Z.(2012).Reliability evaluation of multi-state systems under cost consideration.Applied Mathematical Modelling,36,4261-4270.
19. Ramirez-Marquez, J. E.,Coit, D. W.,Tororella, M.(2006).A generalized multistate-based path vector approach to multistate two-terminal reliability.IIE Transaction,38,477-488.
20. Satitsatian, S.,Kapur, K. C.(2006).An algorithm for lower reliability bounds of multistate two-terminal networks.IEEE Transactions on Reliability,55,199-206.
21. Shrestha, A.,Xing, L.,Coit, D. W.(2010).An efficient multistate multivalued decision diagram- based approach for multistate system sensitivity analysis.IEEE Transactions on Reliability,59,581-592.
22. Yeh, W. C.(2009).A simple universal generating function method to search for all minimal paths in networks.IEEE Transactions on System, Man and Cybernetics,39,1247-1254.
23. Yeh, W. C.(2015).An improved sum-of-disjoint-products technique for symbolic multistate flow network reliability.IEEE Transactions on Reliability,64,1185-1193.
24. Yeh, W. C.(2009).Multistate network reliability evaluation under the maintenance cost constraint.International Journal of Production Economics,88,73-83.
25. Yeh, W. C.(2007).Search for minimal paths in modified networks.Reliability Engineering and System Safety,75,389-395.
26. Zuo, M. J.,Tian, Z.,Hung, H. Z.(2007).An efficient method for reliability evaluation of multi- state networks given all minimal path vector.IIE Transaction,39,473-479.