應用二元決策圖於隨機型流量網路之最快路徑問題的系統可靠度評估

二十一世紀是一個知識爆炸且各類資訊能快速傳遞之時代。欲瞭解這些資訊的傳遞情況，可由現今在作業研究、資訊科學等相關網路議題進行探索，而目前又以供應鏈管理、交通運輸、電腦通訊及商品物流等網路流量之問題最為熱門。藉由以往在網路問題的相關研究內得知，需判斷某一網路系統是否優劣可透過系統可靠度進行分析，故系統可靠度在網路流量問題中扮演極重要之角色。然而，與系統可靠度相關之研究大多以確定型之流量網路系統作為探討對象，但實際生活中確定型流量網路系統卻是相當有限，反而隨機型流量網路系統較常發生於現實生活當中，如電腦網路系統、電子通訊系統等。另外，現今的社會環境對於資源有效分配與時間掌握非常重視，故隨機型流量網路系統往往會加入與資源或時間相關之限制元素（如：各邊 (edge)容量、總傳輸量、傳輸時間等），使該流量網路系統更符合現今各式流量網路之問題，以便人們更加了解問題本身，進而讓人們對於該問題找出對應之解決方案。但上述流量網路問題中（如：最快路徑問題），目前並無一簡便之演算法可供人們使用（即搜尋符合限制條件之路徑）。絕大多數對於最快路徑問題之演算法乃需先求出所有MPs (minimal paths)後，再藉由最小容量的方式才得知該系統之所有可行路徑，進而求得此系統之可靠度，故本研究期望發展Binary Decision Diagram (BDD)為基之演算法 (The BDD-QP algorithm)，該演算法可直接求算出於隨機型流量網路中可將特定數量之資料在固定的限制時間內完整由起點傳送至終點的所有可行路徑。之後，只需計算此流量網路系統所有可行路徑中各邊 (edge)容量所對應之機率，即可得知該流量網路之系統可靠度，以作為後續了解此流量網路是否具穩定可靠之基礎。最後，本研究將以兩個實際範例說明此BDD-QP演算法，並評估其對應之系統可靠度。

關鍵字

系統可靠度；二元決策圖；隨機型流量網路；時間限制；最快路徑問題；最小路徑

並列摘要

無資料

並列關鍵字

system reliability ； binary decision diagram ； multi-state flow networks ； a time limit ； quickest paths problem ； minimal path

參考文獻

[1] A. Rauzy. New algorithms for fault tree analysis. Reliability Engineering and System Safety, 40:203-211, 1993.

[2] B. Bolling, I. Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Computer. vol 45, pp 993-1002, Sep. 1996.

[4] Chen YL, Chin YH. The quickest path problem. Computers & Operations Research, 17:153-61, 1990.

[5] Chen YL. An algorithm for finding the k quickest paths in a network. Computers & Operations Research, 20:59-65, 1993.

[6] Chen YL. Finding the k quickest simples paths in a network. Information Processing Letters, 50:89-92, 1994.

國際替代計量

應用二元決策圖於隨機型流量網路之最快路徑問題的系統可靠度評估

主題瀏覽