臺灣博碩士論文加值系統

運輸路徑規劃的問題中，火力電廠的煤炭運輸路徑規劃是相當複雜的問題，複雜的運輸路徑形成輸煤網路。為了解決國內知名火力電廠煤炭運輸路徑規劃的問題，本研究對火力電廠的輸煤網路進行分析，以最小生成樹建立輸煤網路。分析所有輸煤路徑的轉運模式，提出輸煤路徑演算法，達到在輸煤網路中搜尋最短輸煤路徑之目的。在煤炭的運輸過程中，找出每條輸煤路徑的最高運輸效率，以最大流量最小切割定理，提出輸煤路徑最大流量最小切割演算法，找出每條輸煤路徑的最大流量，達到煤炭運輸最高效率。最後的模擬結果輸出完成規劃的輸煤路徑字串、輸煤路徑權重與最大流量，解決火力電廠運輸路徑規劃的問題。

In the problem of transportation path planning, the thermal power plant coal transportation path planning is a very complex problem. The complex transportation path forms the coal-transportation network. In order to solve the problem of coal transportation path planning in domestic famous thermal power plant, this paper analyzes the coal-transportation network of thermal power plant, with the minimum spanning tree to build coal-transportation network. Analyzes the transport mode of all coal-transportation path. Proposed a coal-transportation path algorithm, to achieve the purpose of searching for the shortest coal-transportation path in the coal-transportation network. In the process of coal transportation, find the maximum transport efficiency of each coal-transportation path. Proposed coal-transportation path maximum-flow minimum-cut algorithm, find the maximum flow of each coal-transportation path, to achieve the maximum transport efficiency. The final simulation results are output to complete the planning coal-transportation path string, coal-transportation path weight and maximum flow, to solve the thermal power plant transportation path planning problem.

摘要 i
ABSTRACT ii
誌謝 iii
目次 iv
表目次 v
圖目次 vi
第一章　緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程 3
第二章　文獻探討 4
2.1 最小生成樹（Minimum Spanning Tree） 4
2.1.1 Kruskal演算法 5
2.1.2 Prim演算法 8
2.2 最短路徑樹（Shortest Path Tree） 11
2.2.1 Dijkstra演算法 11
2.3 深度優先搜尋（Depth-first Search） 16
2.4 動態規劃（Dynamic Programming） 17
2.5 最大流量最小切割定理（Maximum-flow Minimum-cut Theorem） 20
2.6 容錯選路演算法（Fault-tolerant Routing Algorithm） 22
第三章　研究方法 24
3.1 火力電廠輸煤網路的節點結構 24
3.2 火力電廠輸煤網路的圖形 33
3.3 最大同時可行的輸煤路徑分析 38
3.3.1 港口到各個堆煤區分析 38
3.3.2 堆煤區到發電機組的輸煤網路分析 47
3.3.3 港口不經過堆煤區到發電機組（直送）的輸煤網路分析 56
第四章　輸煤路徑演算法 62
4.1 各種不同權重下之路徑規劃 62
4.2 設備故障替代方案之路徑規劃 64
4.3 提出輸煤最短路徑演算法 67
4.4 提出輸煤路徑最大流量最小切割演算法 75
第五章　模擬結果 78
5.1 最短輸煤路徑結果 78
5.2 最大同時可行的輸煤路徑結果 97
5.3 容錯選路的輸煤路徑結果 100
第六章　結論與未來研究方向 106
參考文獻 107
附錄一 111

[1]Yuan-Sheng Huang, Shuang Liu, andLi-Xia Tian, “The analysis of coal port abnormal phenomenon activity network under generalized precedence relations,” in 2012 International Conference on Machine Learning and Cybernetics, 2012, pp. 15–17.
[2]H.Li, W.Mao, A.Zhang, andC.Li, “An improved distribution network reconfiguration method based on minimum spanning tree algorithm and heuristic rules,” Int. J. Electr. Power Energy Syst., vol. 82, pp. 466–473, 2016.
[3]D. P.Montoya andJ. M.Ramirez, “A minimal spanning tree algorithm for distribution networks configuration,” IEEE Power Energy Soc. Gen. Meet., pp. 1–7, 2012.
[4]T. D.Sudhakar andK. N.Srinivas, “Power system reconfiguration based on Prim’s algorithm,” 2011 1st Int. Conf. Electr. Energy Syst. ICEES 2011, no. i, pp. 12–20, 2011.
[5]S.Dimitrijevic andN.Rajakovic, “An innovative approach for solving the restoration problem in distribution networks,” Electr. Power Syst. Res., vol. 81, no. 10, pp. 1961–1972, 2011.
[6]S.Dimitrijevic andN.Rajakovic, “Service Restoration of Distribution Networks Considering Switching Operation Costs and Actual Status of the Switching Equipment,” IEEE Trans. Smart Grid, vol. 6, no. 3, pp. 1227–1232, 2015.
[7]H.Ito, K.Iwama, Y.Okabe, andT.Yoshihiro, “Single backup table schemes for shortest-path routing,” Theor. Comput. Sci., vol. 333, no. 3, pp. 347–353, 2005.
[8]B.Gfeller, N.Santoro, andP.Widmayer, “A distributed algorithm for finding all best swap edges of a minimum-diameter spanning tree,” IEEE Trans. Dependable Secur. Comput., vol. 8, no. 1, pp. 1–12, 2011.
[9]Ajendra Dwivedi, Xinghuo Yu, Peter Sokolowski, Peter Wong, andFulvio Buratto, “Fault Location in Power Networks Using Graph Theory,” in IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics Society, 2010, pp. 2436–2441.
[10]G.Tan, X.Han, andY.Zhao, “Approximate shortest path algorithms for network-tree model,” IEEE Conf. Intell. Transp. Syst. Proceedings, ITSC, vol. 2, pp. 1263–1268, 2003.
[11]X.Wang andC.Ran, “Dynamic Path Planning Algorithm Based on Time-Dependent Road Network,” in 2012 Third Global Congress on Intelligent Systems, 2012, pp. 222–225.
[12]E. P. F.Chan andY.Yang, “Shortest path tree computation in dynamic graphs,” IEEE Trans. Comput., vol. 58, no. 4, pp. 541–557, 2009.
[13]S.Demeyer, P.Audenaert, M.Pickavet, andP.Demeester, “Dynamic and stochastic routing for multimodal transportation systems,” Iet Intell. Transp. Syst., vol. 8, no. 2, pp. 112–123, 2014.
[14]“最大流最小割定理,” 維基百科, 2017. [Online]. Available: https://zh.wikipedia.org/wiki/最大流最小割定理.
[15]R.Tahmasbi, E.Nasrabadi, andS. M.Hashemi, “The value of information in stochastic maximum flow problems,” Comput. Oper. Res., vol. 40, no. 7, pp. 1744–1751, 2013.
[16]K.Otsuki, Y.Kobayashi, andK.Murota, “Improved max-flow min-cut algorithms in a Circular Disk Failure Model with application to a road network,” Eur. J. Oper. Res., vol. 248, no. 2, pp. 396–403, 2016.
[17]M.Panda andP. M.Khilar, “Distributed self fault diagnosis algorithm for large scale wireless sensor networks using modified three sigma edit test,” Ad Hoc Networks, vol. 25, no. PA, pp. 170–184, 2015.
[18]R. P.Grimaldi, Discrete and Combinatorial Mathematics AN APPLIED INTRODUCTION. Terre Haute, Indiana: ADDISON-WESLEY PUBLISHING COMPANY, 1989.
[19]A.Saglam andN. A.Baykan, “Sequential image segmentation based on minimum spanning tree representation,” Pattern Recognit. Lett., vol. 16, no. 0, pp. 34–0, 2016.
[20]L.Georgiadis, “Bottleneck Multicast Trees in Linear Time,” IEEE Commun. Lett., vol. 7, no. 11, pp. 564–566, 2003.
[21]A. K.Ziliaskopoulos, F. D.Mandanas, andH. S.Mahmassani, “An extension of labeling techniques for finding shortest path trees,” Eur. J. Oper. Res., vol. 198, no. 1, pp. 63–72, 2009.
[22]Y.Deng, Y.Chen, Y.Zhang, andS.Mahadevan, “Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment,” Appl. Soft Comput. J., vol. 12, no. 3, pp. 1231–1237, 2012.
[23]B.Joeris, N.Lindzey, R. M.McConnell, andN.Osheim, “Simple DFS on the complement of a graph and on partially complemented digraphs,” Inf. Process. Lett., vol. 117, pp. 35–39, 2017.
[24]D. J.Pearce, “A space-efficient algorithm for finding strongly connected components,” Inf. Process. Lett., vol. 116, no. 1, pp. 47–52, 2016.
[25]M.Dietzfelbinger andR.Jaberi, “On testing single connectedness in directed graphs and some related problems,” Inf. Process. Lett., vol. 115, no. 9, pp. 684–688, 2015.
[26]I.Mahdavi, R.Nourifar, A.Heidarzade, andN. M.Amiri, “A dynamic programming approach for finding shortest chains in a fuzzy network,” Appl. Soft Comput. J., vol. 9, no. 2, pp. 503–511, 2009.
[27]B.Appleton andC.Sun, “Circular shortest paths by branch and bound,” Pattern Recognit., vol. 36, no. 11, pp. 2513–2520, 2003.
[28]蕭志明, “演算法教學:Dynamic Programming,” YouTube, 2013. [Online]. Available: https://www.youtube.com/watch?v=b46hNGTZBco.
[29]“動態規劃(dynamic programming),” MBA智库百科, 2015. [Online]. Available: http://wiki.mbalib.com/zh-tw/动态规划.
[30]Avinash Kamble, “Dynamic Programming Part-1,” YouTube, 2016. [Online]. Available: https://www.youtube.com/watch?v=P68h3lCZaig.
[31]“網路流,” 維基百科, 2016. [Online]. Available: https://zh.wikipedia.org/wiki/网络流.
[32]H.Li, T.Zhang, Y.Zhang, K.Wang, andJ.Li, “A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks,” Ad Hoc Networks, vol. 0, pp. 1–8, 2017.
[33]L. M.Hirsch andJ. F.Schuette, “Graph theory applications to continuity and ranking in geologic models,” Comput. Geosci., vol. 25, no. 2, pp. 127–139, 1999.
[34]J.-S. P.Hong-Chi Shih, Jiun-Huei Ho, Bin-Yih Liao, “Fault Node Recovery Algorithm for a Wireless Sensor Network,” IEEE Sens. J., vol. 13, no. 7, pp. 2683–2689, 2013.
[35]A.Mahapatro andP. M.Khilar, “Fault Diagnosis in Wireless Sensor Networks: A Survey,” IEEE Commun. Surv. Tutorials, vol. 15, no. 4, pp. 2000–2026, 2013.
[36]H.Gu, J.Zhang, K.Wang, Z.Liu, andG.Kang, “Enhanced fault tolerant routing algorithms using a concept of ‘balanced ring,’” J. Syst. Archit., vol. 53, no. 12, pp. 902–912, 2007.
[37]T.Čičić, “On basic properties of fault-tolerant multi-topology routing,” Comput. Networks, vol. 52, no. 18, pp. 3325–3341, 2008.
[38]J.Wu, F.Dai, X.Lin, J.Cao, andW.Jia, “An extended fault-tolerant link-state routing protocol in the internet,” IEEE Trans. Comput., vol. 52, no. 10, pp. 1298–1311, 2003.