An Algorithm to Approximate the Reliability of a Flow Network

流量網路可靠度之近似值演算法

10.29977/JCIIE.200301.0004

簡進嘉(Chin-Chia Jane)；賴藝文(Yih-Wenn Laih)

近似值演算法 ； 流量網路 ； 可靠度分析 ； 實例驗證 ； approximation algorithm ； flow network ； reliability ； computational experiments

工業工程學刊

20卷1期（2003 / 01 / 01）

21 - 26

英文

流量網路可靠度（網路系統上供應結點能滿足需求結點所指定需求量的機率值）爲流量網路系統設計規劃時的重要參考準則之一。本文提出演算法以計算流量網路之可靠度的近似值。由於流量網路之可靠度問題為一NP-hard的問題，因此當網路系統愈大時，要計算正確的可靠度必須得花用成指數增長的時間。為求在較短時間內完成計算，本文改進Jane & Yuan近期所提出的正確互次項和的演算法，以計算流量網路之可靠度值的上限及下限，進而求得在所設定上下限差額值下的可靠度近似值。本文亦進行實例驗證，以說明及探討所提出演算法之性質。

This article presents dynamic lower and upper bounds for approximating the s-t reliability, the probability that source node s can supply a specified demand to sink node t, of a flow network. The proposed algorithm which is motivated by Jane and Yuan’s exact algorithm can be applied to networks with non-uniform probability of arc failure, and, in addition, can be applied to solve the well-studied NP-hard terminal-pair reliability problem. Computational experiments are conducted and discussed. Since related work on bounding the s-t reliability problem is rare, the proposed algorithm, which presents a first step in the research of efficient approximation algorithms, is worthwhile.

1. Aggarwal, K. K.,Chopra, Y. C.,Bajwa, J. S.(1982).Capacity consideration in reliability analysis of communication systems.IEEE Transactions on Reliability,31
2. Colbourn, C. J.(1987).The Combinatorics of Network Reliability.New York:Oxford University Press.
3. Doulliez, P.,Jamoulle, E.(1972).Transportation networks with random arc capacities.Revue Francaise d'Automatique, Informatique et Recherche Operationnelle,2
4. Ford, L. R.,Fulkerson, D. R.(1962).Flows in Networks.Princeton, New Jersey:Princeton University Press.
5. Hu, Te Chiang(1982).Combinatorial Algorithms.Massachusetts:Addison-Wesley.
6. Locks, M. O.(1982).Recursive disjoint products: A review of three algorithm.IEEE Transactions on Reliability,31
7. Provan, J. S.,Ball, M. O.(1984).Computing network reliability in time polynomial in the number of cuts.Operations Research,32
8. Rai, S.,Soh, S.(1991).A computer approach for reliability evaluation of telecommunication networks with heterogeneous link-capacities.IEEE Transactions on Reliability,40
9. Rueger, W. J.(1986).Reliability analysis of networks with capacity constraints and failure at branches ＆ nodes.IEEE Transactions on Reliability,35
10. 簡進嘉 Jane, Chin-Chia,阮約翰 Yuan, John(2001).A sum of disjoint products algorithm for reliability evaluation of flow networks.European Journal of Operational Research,131