Reliability Evaluation of Multi-State Quick Path Flow Networks

多狀態流量網路之可靠度評估

葉維彰(Wei-Chang Yeh) ； 林伶恩(Ling-En Lin) ； 陳逸群(Yi-Chun Chen)

《品質學報》 20卷2期 (2013/04) Pp. 199-215

https://doi.org/10.6220/joq.2013.20(2).03

摘要

網路可靠度是指網路中的起點與終點連結成功之機率。世界上有許多系統都應用了網路架構，例如網際網路、電力傳輸及配銷系統。為了使系統運作順暢，網路可靠度的評估是非常重要的。網路可靠度亦可代表配銷系統中準時達交的機率。為了估計一個恰當的指標，本文以全面搜尋法取代傳統文獻在事先定義的最小路徑中搜尋的方式。傳統文獻中的解決方案局限於不交集的最小路徑，本研究則放寬此限制條件，提出新的演算法。在此模型中，商品可透過一條最小路徑傳送；也可以分割為數條路徑傳送，路徑彼此間可交集。

關鍵字

多狀態 ； 最小路徑 ； 不交集最小路徑 ； 品質指標 ； 網路可靠度

並列摘要

Network reliability refers to the probability that a live connection exists between a source node and a sink node. Network structures are applied extensively in many real-world systems, such as computers, power transmission, and distribution systems. Therefore, reliability evaluation of a general network is very important. Network reliability can be adopted as an index of network quality to indicate the probability of successful on-time delivery. To estimate an adequate index for network quality, we search for all feasible combinations instead of a pre-defined minimal path (MP) set which appeared on literature. This study considers the quick path problem within the multi-state flow network (MQPFN). It tries to locate all feasible solutions and evaluate the probability that d units of commodities can be sent from the source node to the sink node through MQPFN within T units of time. Commodities may be transmitted via single or multiple MPs, and solutions are not subject to disjointed MPs. This study contributed to develop a new algorithm which not only finds for all quick path (QPs) to transmit commodities on time via a network, but also accurately evaluates the probability of successful delivery as an index of network quality.

並列關鍵字

minimal path ； quality index ； network reliability ； multi-state ； quick path

參考文獻

Aven, T.(1987).Availability evaluation of oil gas-production and transportation systems.Reliability Engineering & System Safety.18(1),35-44.

Aven, T.(1988).Some considerations on Reliability Theory and its applications.Reliability Engineering & System Safety.21(3),215-223.

Chen, G. H.,Hung, Y. C.(1993).On the quickest path problem.Information Processing Letters.46(3),125-128.

Chen, G. H.,Hung, Y. C.(1994).Algorithms for the constrained quickest path problem and the enumeration of quickest paths.Computers & Operations Research.21(2),113-118.

Chen, Y. L.,Chin, Y. H.(1990).The quickest path problem.Computers & Operations Research.17(2),153-161.