臺灣博碩士論文加值系統

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

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.

中文摘要.........................................................................................................................i
Abstract.........................................................................................................................ii
Table of Contents........................................................................................................iii
List of Figures...............................................................................................................v
List of Tables...............................................................................................................vi
Chapter 1 Acronyms, notations, nomenclature and assumptions...........................1
1.1 Acronyms.........................................................................................................1
1.2 Notations..........................................................................................................1
1.3 Nomenclature...................................................................................................8
1.4 Assumptions.....................................................................................................9
Chapter 2 Introduction..............................................................................................10
2.1 Background and Motivation...........................................................................10
2.2 Problem Statement and Objectives.................................................................12
2.3 Overview of This Thesis................................................................................12
Chapter 3 Literature Review.....................................................................................14
3.1 The quickest path algorithm...........................................................................14
3.2 The k shortest paths........................................................................................17
3.3 Multi-State Quickest Path Flow Network and Reliability Evaluation...........20
Chapter 4 Lemmas and theorems.............................................................................24
4.1 The Multi-State Quickest Path Flow Network and Reliability Evaluation......24
4.2 The Multi-State Quickest Path Flow Network and Reliability Evaluation with cost constraint.........................................................................................................26
Chapter 5 The algorithm...........................................................................................29
5.1 The algorithm for the Multi-State Quickest Path Flow Network Reliability...29
5.2 The algorithm for the Multi-State Quickest Path Flow Network Reliability with cost constraint...........................................................................................31
Chapter 6 An Illustrative Example...........................................................................35
6.1 An example for the Multi-State Quickest Path Flow Network Reliability......35
6.2 An example for the Multi-State Quickest Path Flow Network Reliability with cost constraint...................................................................................................39
Chapter 7 Conclusions and Future works...............................................................43
7.1 Conclusions......................................................................................................43
7.1.1 Conclusions for the Multi-State Quickest Path Flow Network Reliability
Algorithm.....................................................................................................43
7.1.2 Conclusions for the Multi-State Quickest Path Flow Network Reliability
Algorithm with cost constraint.....................................................................44
7.3 Future works.....................................................................................................45
References...................................................................................................................46

[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.
[6] T Aven. Availability evaluation of oil/gas production and transportation systems. Reliab Eng 1987;18:35–44.
[7] T Aven. Some considerations on reliability theory and its applications. Reliab Eng Syst Saf 1988;21:215–23.
[8] WC Yeh. An improved algorithm for searching all minimal cuts in modified networks. Reliability Engineering and System Safety 2008;93:1018–1024.
[9] CJ Colbourn. The combinatorics of network reliability. New York: Oxford University Press; 1987.
[10] M.H Moore. On the fastest route for convoy-typetralficin flowrate-constrained networks. Transport Sci 1976; 10:113–124.
[11] EQV Martins, JLE dos Santos. An algorithm for the quickest path problem. Operations Research
Letters 1997;20:195–198.
[12] Y. L. Chen and Y. H. Chin. The quickest path problem. Computers & Operations Research
1990;17(2):153–161.
[13] J. B. Rosen, S. Z. Sun and G. L. Xue. Algorithms for the quickest path problem and the enumeration of quickest paths. Computers & Operations Research 1991;18(6):571–584.
[14] MMB Pascoal, MEV Captivo, JCN Clímaco. A comprehensive survey on the quickest path problem. Annals of Operations Research 2006;147:5–21.
[15] YK Lin. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Computers & Operations Research 2003; 30: 567–575.
[16] D Eppstein. Finding the k Shortest Paths. SIAM JOURNAL ON COMPUTING 1998;28(2):652–673.
[17] WC Yeh. A Simple Heuristic Algorithm for Generating All Minimal Paths. IEEE TRANSACTIONS ON RELIABILITY 2007;56(3):488–494.
[18] JC Hudson, KC Kapur. Reliability bounds for multistate systems with multistate components. Operations Research 1985;33:153–60.
[19] R Yarlagadda, J Hershey. Fast algorithm for computing the reliability of communication network. International Journal of Electronics 1991;70:549–64.
[20] GH Chen, YC Hung. Algorithms for the constrainedquickest path problem andthe enumeration of quickest paths. Computers & Operations Research 1994;21:113–8.
[21] GH Chen, YC Hung. On the quickest path problem. Information Processing Letters 1993;46:125–8.