利用Dijkstra演算法與最大流量最小切割定理解決運輸路徑規劃的問題

陳大仁 ； 王秉豐 ； 陳宏昌 ； 陳曄徵

《TANET2017 臺灣網際網路研討會》 2017年 (2017/10) Pp. 1345-1351

https://doi.org/10.6728/TANET.201710.0234

摘要

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

關鍵字

運輸路徑規劃 ； 輸煤網路 ； 輸煤路徑 ； 最小生成樹 ； Dijkstra演算法 ； 最大流量最小切割定理

並列摘要

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 coaltransportation 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 coaltransportation path maximum-flow minimum-cut algorithm, find the maximum flow of each coaltransportation 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.

並列關鍵字

Transportation path planning ； Coaltransportation network ； Coal-transportation path ； Minimum spanning tree ； Dijkstra's algorithm, Maximum-flow minimum-cut theorem