# 臺灣博碩士論文加值系統

(35.172.223.251) 您好！臺灣時間：2022/08/16 23:30

:::

### 詳目顯示

:

• 被引用:0
• 點閱:446
• 評分:
• 下載:102
• 書目收藏:2
 本文介紹一種解決最短路徑問題的數值演算法，首先藉由流向表之觀念將網路結構轉換為二維式數據結構，以利數值儲存與處理。接著透過梯式數值運算，可以轉換得出最小擴張樹，以及迴路鏈集之架構，最後藉著虛構路徑之助即可求出最短路徑解答。 本文所提出之演繹法以MATLAB軟體處理做實例之解釋，對於網路拓撲複雜之最短路徑搜索問題上，可由此演算法加以解決。本演算法在於節省最短路徑問題之運算處理過程，並可運用於作業研究、運輸問題，及電腦網路之連線維護作業上。
 This paper presents an innovative numerical method of the shortest path problem for a network. Firstly, the topological structure of a network is converted into a two-dimensional data structure via Flow-table so that data storage and numerical processing can easily be made. Secondly, by the Echelon form processing, Minimum Span Tree and Tie-set links of the network under studied can be identified. Finally, by taking advantages of a hypothetical path, the shortest path of the network can then be obtained. The proposed method in this paper is also illustrated by a numerical example via MATLAB software. The shortest path for a large network with complex topology can be solved by the proposed method with easy-processing features. The method is applicable to the fields of operations research, transportation management, and computer networking.
 目錄 圖目錄………………………………………………………………………………...Ⅵ 表目錄………………………………………………………………………………...Ⅶ 第一章 緒論…………………………….……………………………….………….1 1.1 研究動機與目的……………………………………………..……….……..1 1.2 本文特點………………..……………………………………..…..…….......2 1.3 研究範圍………………..…………………………………….…..………....2 1.4 研究方法及論文架構…..………………………………….………..……....3 第二章 最小擴張樹與最短路徑之問題及文獻回顧…………………........4 2.1 最小擴張樹問題…………..……………………….…………………..…....4 2.2 最小擴張樹問題的一些基本概念……………………………....………….5 2.3 最小擴張樹之最佳化……………………………….……....………………7 2.4 最小擴張樹演算法之文獻回顧……………………………….……....……9 2.5 最短路徑…………………………………….……....……………………..10 2.6 最短路徑演算法之文獻回顧…………………..………………………….13 2.7 最短路徑之演算法探討……………………..……………………….……16 第三章 最小擴張樹問題之數值方法……………….………….…………....18 3.1 流向表架構………………..……………………….……………………....18 3.2 入映矩陣………….………………………………………………………..18 3.3 先標處理…………………………………………………………………...19 3.4 梯式流向表………………………………………………………………...20 3.5 後標處理…………………………………………………………………...21 3.6 最小擴張樹型態…………………………………………………………...21 3.7 最小擴張樹之演繹步驟………………………………………………...…23 3.8 不考慮分支方向性之最小擴張樹求法……………………….…………..28 3.9 小結………………………………………………………………………...32 第四章 最短路徑問題之數值方法………………………….………….…….33 4.1 迴路鏈集矩陣………………..…………………………………………….33 4.2 最短路徑解答…..………………………………………………………….33 4.3 路徑判斷原則……………………..……………………………………….34 4.4 最短路徑之演算法………..……………………………………………….34 4.5 釋例……………..………………………………………………………….35 4.6 小結……………..………………………………………………………….43 第五章 多目標限制情況下之最短路徑解法……………….…………..….44 5.1 簡介……………………..………………………………………………….44 5.2 本文方法……..…………………………………………………………….44 5.3 釋例……………………..………………………………………………….46 5.4 小結…………………………………..…………………………………….53 第六章 結論與建議………………………………………….…………...……...54 6.1 結論……………………..………………………………………………….54 6.2 建議……………………..………………………………………………….55 參考文獻 ………………………………………………….......…………………….56 圖目錄 圖2-1 擴張樹之說明……….…………………………………………………………6 圖2-2 擴張樹特質說明…….…………………………………………………………7 圖2-3 切集與路徑最佳化狀況….……………………………………………………8 圖2-4 網路圖脈例子…………....………………………………………………...….11 圖2-5 網路方向性之說明………….…………………………………………….….12 圖2-6 網路圖A…………….……………………………………………………...…13 圖3-1 網路圖B……………….…………………………………………………...…18 圖3-2 網路圖C……..……………………………………………………...………...24 圖3-3 具有方向性之網路圖C.…………………………………………………...…24 圖3-4 加入虛構路徑之網路圖C.………………………………………………...…26 圖3-5 具方向性之網路圖C的最小擴張樹架構……………………………………27 圖3-6 加入虛構路徑之網路圖C……………………………………………...…….29圖4-1 網路圖D…………....……………………………………………….……...…36 圖4-2 加入虛構路徑之網路圖D.………………………………………………...…38 圖4-3 網路圖D之最小擴張樹架構.………………………………………………...40 圖5-1 網路圖E………………….…………....………………………………...…....46 圖5-2 加入虛構路徑之網路圖E.………………………………………………...…47 表目錄 表3-1 圖3-1的入映矩陣A……………………………………………………..……19 表3-2 流向表Q………………..…………………………………………………..…19 表3-3 梯式流向表 …………………………………………………………………20 表3-4 梯式流向表S………………………………………………………….………21 表3-5 標準切集矩陣型態…………………………………………………………...22 表3-6 圖3-3之入映矩陣A……………………………………………………..……25 表3-7 加入虛構路徑之入映矩陣 ………………………………………………..25 表3-8 圖3-4之流向表Q…...………………………………………………………..26 表3-9 圖3-4之梯式流向表 ….…………………………………………………….27 表3-10 網路圖C之入映矩陣A.…………………………………………………….28 表3-11 圖3-6之入映矩陣 ………………………………………………………..29 表3-12 圖3-6之流向表Q……………………………………………………………30 表3-13 圖3-6之梯式流向表 ..……………………………………………………..30 表3-14 圖3-6之梯式流向表S………………………………………………………31 表4-1 倉庫間的運送計畫表………………………………………………………...36 表4-2 網路圖D之入映矩陣A……………………….……………………………...37 表4-3 圖4-2之入映矩陣 ……….………………………………………………...37 表4-4 圖4-2之流向表Q…..………………………………………………………....38 表4-5 圖4-2之梯式流向表 ……...………………………………………………...39 表4-6 圖4-2之梯式流向表S……...………………………………………………...39 表4-7 圖4-2之矩陣T……...………………………………………………………...40 表4-8 圖4-2之流向表P……………...……………………………………………...41 表4-9 線性相加後所形成的路徑……...…………………………….……………...41 表5-1 運輸時間限制下之入映矩陣 ……...…………………………….………..48 表5-2 運輸時間限制下之最小擴張樹型態……...……………………………..…..48 表5-3 運輸時間限制參數下所形成的路徑……...………………………………....49 表5-4 運送時間限制下所形成的路徑說明與其運送時間……...…………………49 表5-5 運輸成本限制參數下的入映矩陣A……...………………………………....50 表5-6 運輸成本限制參數下所形成的路徑……...………………………………....51 表5-7 運送成本限制下所形成的路徑說明與其運送成本……...………………....51 表5-8 符合運送時間限制的路徑在成本與距離之說明……...…………………....52 表5-9 符合運送成本限制的路徑在時間與距離之說明……...…………………....52
 參考文獻[1] Bellman R., “On a routing problem,” Quarterly of Applied Mathematics, Vol. 16, pp. 87-90, 1958.[2] Berge C., and A. Ghouila-Houri, Programming and Transportation Networks, N.Y. : Wiley, 1962.[3] Chua L. C., and P. M. Lin, Computer Aided Analysis of Electronic Circuit, Prentice Hall, 1975.[4] Dial R., “Shortest path forest with topological ordering,” Communication of ACM, Vol. 12, pp. 632-633, 1969.[5] Dial R., F. Glover, D. Karney, and D. Klingman, “A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees,” Networks, Vol. 9, pp. 215-248, 1979.[6] Dijkstra E., “A note on two problems in connection with graphs,” Numeriche Mathematics, Vol. 1, pp. 269-271, 1959.[7] Divoky J. J. and M. S. Hung, “Performance of shortest path algorithms in network flow problems,” Management Science, Vol. 36, pp. 661-673, 1990.[8] Ford L. R., and D. R. Fulkerson, “Solving the transportation problem,” Management Science, Vol. 3, pp. 24-32, 1956.[9] Gallo G., and S. Pallottino, Shortest path methods in transportation planning models, In Transportation Planning Models, 1984.[10] Gallo G., and S. Pallottino, In Fortran Codes for Network Optimization, “Shortest path algorithms,” Annals of Operations Research, Vol. 13, pp. 3-79, 1988.[11] Hung M. S. and J. J. Divoky, “A computational study of efficient shortest path algorithms,” Computers and Operations Research, Vol. 15, pp. 567-576, 1988.[12] Juang J. Y., “Identifying Topological Structure of a Large Scale Dynamic Network System,” Proc. International Conference on Advanced Automation, pp. 398-402, 1983.[13] Juang J. Y., “Identifying Minimum Span of a Network by Flow Table,” Proc. International Conference on Advanced Automation, pp. 1130-1134, 1984.[14] Katta G. Murty, Network Programming, Englewood Cliffs, N. J. : Prentice Hall, 1992.[15] Kruskal J. B., “On the shortest spanning tree of graph and the traveling salesman problem ,” Proc. of the American Mathematical Society, Vol. 7, pp. 48-50, 1956.[16] Prim R. C., “Shortest connection networks and some generalization,” Bell System Technical Journal, Vol. 36, pp. 1389-1401, 1957.[17] 賴嘉旭，“多重限制條件下最短路徑問題之研究”，私立淡江大學管理科學研究所碩士論文，中華民國八十一年。[18] 陳慧琪，“時間相依最短路徑問題演算方法之研究”，國立交通大學運輸工程與管理系碩士論文，中華民國八十八年。
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 時間相依最短路徑問題演算方法之研究 2 多重限制條件下最短路徑問題之研究 3 以集線器為基礎網路拓樸之研究

 1 6.李清榮，「電業自由化下之電力市場競爭發展趨勢」，能源季刊，第28卷第2期，民國87年4月。 2 5.許志義，「台灣電業自由化改革架構之研擬」，能源季刊，第26卷第3期，民國87年7月。 3 4.陳浪潮，「台灣能源產業自由化的理論探討」，能源季刊，第28卷第1期，民國87年1月。

 1 權重式最短路徑應用於捷運導航 2 運用最短路徑演算法與動態資訊進行大眾運輸行前旅次規劃 3 以三角剖分為基礎之最短路徑演算法 4 考慮時窗限制之多車種零擔貨運車輛途程問題 5 液態培養生產靈芝菌絲體與靈芝多醣最適化之研究 6 考慮禁止路徑的最短路徑演算法 7 最短路徑演算法實作 8 公營機關員工對IS0-14001變革態度之探討 9 應用模糊多準則決策於我國國際商港公文電子化方案評估之研究 10 台灣地區國際商港港埠營運轉型電子商務模式之研究 11 臺灣地區娛樂漁業漁船載客之適法性研究 12 省自來水公司及各區管理處經營效率之研究─DEA之應用 13 國際商港棧埠業務民營化相關法律適用之研究 14 模糊多準則評量模式-以公務人員平時考核為例 15 提高港勤船舶可用率之研究--以基隆港為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室