Extend the Quickest Path Problem to the Reliability Estimation for Weighted Multi-commodity Multistate Flow Networks

延伸最快路徑問題於權重多商品多階流量網路之可靠度評估

廖鎔熠(Jung-Yi Liao)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2009年)

https://doi.org/10.6843/NTHU.2009.00095

摘要

隨著科技之進步，所需之運算的資訊量愈來愈龐大與複雜，而資料彼此之間的鏈結關係程度亦相對提高，因而此鏈結結構系統可視為一個網路系統。而如何評估此網路系統可以正常的運作，可靠度是一項相當重要的水準指標。網路可靠度不管在實務上和理論上均扮演著重要的角色，亦是學者們紛紛應論之議題。然而，網路可靠度之評估為一個高度複雜之問題，為一NP-hard問題。

多商品流量網路設計問題在實際中有很多廣闊的應用背景，如交通運輸、物流網路、電信網路及生產系統等領域，這些相關應用中，多種產品（貨物、數據、人等）通過有容量限制的網路，各自從起運送至終點，在這類多商品流量模型中，一般假定商品的運送起點和終點之間任何一條路徑都可以用來運送商品，然而有些實際應用問題對運送商品的路徑提出了額外要求，如電信網路設計中，將呼叫方和被呼叫方的通話定義為商品，然而對於該類商品的運送路徑，則需要考慮時間延遲或可靠性等問題。然而，在此研究中，提出了一個新型網路－權重多商品多階最快路徑流量網路。因為了更貼近現實狀況，其路徑或稱為邊對於每一種不同商品給予權重的因子，在邊上也有設有前置時間。在求網路可靠度之前，必需要找出需求量Dp=(d1,d2,…,dp) 在T 時間下能從供給點送達至需求點，然而找出真正的(Dp; T)-MP，以計算網路可靠度。

關鍵字

多商品流量網路 ； 權重多商品多階最快路徑流量網路 ； 網路可靠度

並列摘要

With the advance of technology, a large amount of information required to be computed become more and more complex. The level of information complexity can be regarded as a network system. Network reliability plays an important role in both practical and theoretic aspects. Hence, network reliability becomes a popular issue for many researches to involve in. However, network reliability evaluation is a highly complex problem, also seen as NP-hard problems.

In the past, the quickest path network problem was based on only one commodity, and the multi-commodity flow problems were solved by assuming that the arcs of the flow network are deterministic. However, the capacity of each arc is stochastic in many real-life networks. The weighted multi-commodity multistate-flow quickest-path network (WMMQN) is a novel network composed of multistate components (arcs) capable of transmitting different types of commodities where capacity weight varies with arcs which come along with their own lead time. This paper proposes a simple algorithm to calculate the probability that a flow network with a source node satisfies a specified demand Dp=(d1,d2,…,dp) at the sink node within T units of time, where dq is the demand of commodity q. Such a probability is called the multi-commodity reliability and is dependent on the capacities of arcs. An example is given to illustrate how to generate all lower boundary points for (Dp; T) so as to compute the multi-commodity reliability.

並列關鍵字

Network reliability ； quickest path network ； multi-commodity flow network ； weighted multi-commodity multistate-flow quickest-path network (WMMQN)

參考文獻

[1] Aven T. Availability evaluation of oil/gas production and transportation systems. Reliability Engineering 1987;18:35–44.

[2] Aven T. Some considerations on reliability theory and its applications. Reliability Engineering & System Safety 1988;21:215–23.

[3] Roberts FS, Hwang FK, Monma C. Reliability of computer and communication networks. DIMACS series in discrete mathematics and theoretical computer science, vol. 5. AMS/ACM publisher; 1991.

[4] Ke WJ, Wang SD. Reliability evaluation for distributed computing networks with imperfect nodes. IEEE Transportation Reliability 1997;46:342–9.

[5] Colbourn CJ. The combinatorics of network reliability. New York: Oxford University Press; 1987.