多階最快路徑流量網路在成本限制下的可靠度評估

The Multi-State Quickest Path Flow Network and Reliability Evaluation under Cost Constraints

丘全煒(Chuan-Wei Chiu)

指導教授 ： 葉維彰

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

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

摘要

最快路徑問題為尋找一條在給定的資料量下，由起點傳輸資料到終點需時最短的路徑。為了能夠更符合現實世界當中的系統，例如交通運輸系統與供應鏈管理系統，我們假設在這些系統當中，邊的容量是隨機性的（多階的）。在本研究當中，首先，我們將提出計算d單位的資料可以在T單位時間內由起點傳輸到終點的機率的新式演算法，使用到了k條最短路徑問題的演算法，而所提出的演算法相較於之前提出的方法，擁有較小的時間複雜度，且之前的方法必須先求出圖形當中的所有最小路徑，這個問題本身即為一非確定性多項式難度的問題。之後，我們將原本問題加入了成本限制，擴充為計算d單位的資料可以在T單位時間內由起點傳輸到終點且總成本不能超過c的機率。之後將對上述的兩個問題，附上使用所提出的演算法來計算多階最快路徑流量網路可靠度的範例。

關鍵字

可靠度 ； 多階最快路徑流量網路 ； k條最短路徑

並列摘要

The quickest path problem is to find a path to send a given amount of data from the source node to the sink node with minimum transmission time. In order to conform to the real world systems such as distribution systems and supply chain management system, we assume the capacity of each arc is stochastic (multi-state). In this study, (1) we propose a new algorithm to evaluate the probability that d units of data can be sent from the source node to the sink node through the multi-state quickest path flow network within T units of time. The proposed algorithm based on the k shortest paths algorithm only has less time complexity than the best-known algorithms which were required to solve the NP-hard problem to find all minimal paths in advance. (2) Add cost constraint and extend the problem to evaluate the probability that d units of data can be sent from the source node to the sink node through the multi-state quickest path flow network within time (T) and total cost (c) constraints. Two examples is given to illustrate how multi-state quickest path flow network reliability is evaluated using the proposed algorithm.

並列關鍵字

Reliability ； Multi-state quickest path flow network ； k shortest paths

參考文獻

[1] MA Samad. An efficient algorithm for simultaneously deducing MPs as well as cuts of a communication network. Microelectron Reliab 1987;27:437–41.

[2] P Kubat. Estimation of reliability for communication/computer networks simulation/analytical approach. IEEE Trans Commun 1989;37:927–33.

[3] S Rai, S Soh. A computer approach for reliability evaluation of telecommunication networks with heterogeneous link-capacities. IEEE Trans Reliab 1991;40:441–51.

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

[5] P Doulliez, E Jalnoulle. Transportation network with random arc capacities. RAIRO, Rech Oper Res 1972;3:45–60.