(3.236.222.124) 您好！臺灣時間：2021/05/11 09:01

### 詳目顯示:::

:

• 被引用:1
• 點閱:374
• 評分:
• 下載:0
• 書目收藏:0
 本文主要是探討最短路徑問題，是求在平面上找出指定的節點間之最短連接線段，以供做為各領域之路徑使用，現今，最短路徑的求解方法有許多種，但並不能準確的建構出真正的最短路徑，因此有許多學者嘗試求解出較佳的近似解，以供各領域參考。一般研究所探討的最短路徑問題，其各節點所連接的路徑，皆為連續型線段，此方法卻並未加以考量路徑限制問題，如:障礙物、限制路徑等問題，這些問題使得線段成現不連續型線段，並增加演算過程的複雜化，因而衍生出將實際路徑結合網格圖(Raster graphics)的方式求解，並利用網格圖上的線段，來建構問題的節點與不連續線段，以便求解，本文將問題建構在網格圖上，嘗試應用網格圖結合本文建構的演算法來找出逼近解圖形。本文與一般研究所探討的最短路徑問題不同，是在不連續線段上面，搜尋最短的重複路徑來建構最短路徑問題，應用不連續線段上的水平及垂直座標來連接不連續線段，結合線段修正法來優化路徑，並利用節點的自由度(degree)來做為重複路徑的依據，找出較佳的最短路徑，最後運用本文所建構的演算法應用在不連續線段圖形中，經由不同起點所建構的最短路徑，本文找出了一個在不連續線段下，較佳的逼近解。
 The objective of this research is to solve the shortest path problem on a rectangular graph system that offers applications in various areas. Shortest path is a popular topic in research and many successful algorithms have been established. However, new types of shortest path problems are found recently and most of them are still unsolved. The shortest connection of discontinuous line segments on a rectangular coordinate system is a new type of problem that has significant difference from the traditional shortest path problem. The existing algorithms cannot give a successful solution to this problem. In order to solve this problem, a new algorithm is proposed in this research.The basic property of the connection of discontinuous line segments is that each junction of the connection path must have an even degree. Follow the basic property, the essence of the proposed algorithm is to keep revising the connecting path until the total path length reaches the given criterion. The proposed algorithm is tested by a practical linking problem on a PC board. The result shows that the proposed algorithm is effective.
 中文摘要 ---------------------------------------------- iAbstract --------------------------------------------- ii誌謝 ---------------------------------------------- iii目錄 ---------------------------------------------- iv表目錄 ---------------------------------------------- vi圖目錄 ---------------------------------------------- vii第一章 緒論------------------------------------------ 11.1 研究背景-------------------------------------- 11.2 研究目的-------------------------------------- 21.3 研究條件限制---------------------------------- 21.4 研究方法與步驟-------------------------------- 3第二章 相關文獻探討---------------------------------- 62.1 前言------------------------------------------ 62.2 警察巡邏勤務---------------------------------- 62.2.1 巡邏勤務定義---------------------------------- 72.2.2 巡邏勤務目的---------------------------------- 82.2.3 巡邏勤務內容---------------------------------- 92.2.4 巡邏勤務的方式-------------------------------- 102.2.5 警察巡邏相關研究------------------------------ 122.3 中國郵差問題---------------------------------- 132.3.1 中國郵差問題的求解策略------------------------ 142.4 車輛途程問題---------------------------------- 152.4.1 車輛途程問題的求解策略------------------------ 162.5 最短路徑問題---------------------------------- 182.5.1 K條最短路徑問題------------------------------- 202.5.2 禁止路徑問題---------------------------------- 22第三章 研究方法-------------------------------------- 233.1 名詞解釋與定義-------------------------------- 233.2 問題說明-------------------------------------- 263.2.1 演算法流程------------------------------------ 303.3 建立Raster graphics--------------------------- 313.3.1 曼哈頓距離(Manhattan distance)---------------- 323.4 可行路徑的建構-------------------------------- 333.4.1 可行路徑的修正-------------------------------- 363.5 重複路徑演算法-------------------------------- 383.6 交疊線段-------------------------------------- 443.6.1 正交四邊形繞法-------------------------------- 453.6.2 正交重覆路徑走法------------------------------ 483.6.3 正交重複路徑走法與正交四邊形繞法的比較與應用-- 503.7 不規則線段------------------------------------ 513.7.1 不規則線段的重複路徑建構---------------------- 563.7.2 不規則交疊線段的重複路徑走法------------------ 563.8 研究方法彙整---------------------------------- 57第四章 實驗與討論------------------------------------ 604.1 實驗介紹-------------------------------------- 604.1.1 路徑圖的建構---------------------------------- 614.1.2 路徑圖的可行路徑建構-------------------------- 624.1.3 可行路徑的線段修正---------------------------- 644.1.4 最短重複路徑圖-------------------------------- 664.2 不同起、終點之研究---------------------------- 674.3 最短重複路徑問題比較-------------------------- 684.4 討論總結-------------------------------------- 70第五章 結論與未來發展-------------------------------- 715.1 結論------------------------------------------ 715.2 未來與展望------------------------------------ 72文獻參考 ---------------------------------------------- 73Extended Abstract--------------------------------------- 76簡歷(CV) ----------------------------------------------- 80
 [1] 丁華淵(2007)，考慮靜止路徑的最短路徑演算法，國立台灣科技大學資訊管理系，碩士論文[2] 尤國楨 (2002)警察巡邏管理制度之研究：以臺北縣警察局為例，中國文化大學政治研究所，碩士論文[3] 王建亞、游清柱、陳海燕、陳志超 (2007)，利用基因演算法解決警用巡邏箱選址問題-以台中市立人派出所為例，中華民國九十六年全國計算機會議，台中，中華民國，十二月二十，二十一[4] 林育甫(2006)，利用K條最短路徑預測為新成之代謝途徑，國立成功大學資訊管理研究所，碩士論文[5] 林志誠(2007)，警察巡邏勤務實施成效之研究─從問題導向警政策略探討，銘傳大學社會科學院國家發展與兩岸關係碩士在職專班，碩士論文[6] 林家慶(2008)，在實踐限制下有效率地探勘前K條最短路徑，國立成功大學資訊重研究所，碩士論文[7] 林潔妤(2008)，斐氏圖軟體撰碼問題動規範測式系統的設計與實驗，國立交通大學工業工程與管理學系，碩士論文[8] 吳建興(2000)，3D網格圖最短路徑規劃，國立海洋大學電機工程學系，碩士論文[9] 施建龍(2005)，動態環境網格圖上最佳路徑之規劃，國立台灣海洋大學資訊工程學系研究所，碩士論文[10] 許聖臣(1981)，警察勤務，中央警官學校出版12月出版[11] 許晉嘉(2003)，宅配業或物配送路線規劃問題之研究，國立成功大學交通管理科學研究所，碩士論文[12] 郭文川(2001)，結合PERT與TSP方法於巡邏路線選定之研究─以南投縣警察局之警區分局為例，中英警察大學叢刊[13] 郭秋泔(2004)，考慮旅行時間限制下之隨機旅行銷售原問題─以國際快遞業為例，國立高雄第一科技大學運輸與倉儲營運系，碩士論文[14] 黃冠舜(2012)，權重式最短路徑應用於捷運導航，國立雲林科技大學電機工程系，碩士論文[15] 陳思齊(2007)，巡邏車輛途程問題，國立中央大學土木工程學系，碩士論文[16] 陳海燕、王建亞、游清柱、陳志超 (2007)「利用基因演算法解決警用巡邏箱選址問題-以台中市立人派出所為例」，中華民國九十六年全國計算機會議，台中，中華民國，十二月二十，二十一[17] 陳諺諭(2012)，正交系統中不連續線段之最短路徑之研究，國　　 立虎尾科技大學工業工程與管理研究所，碩士論文[18] 黃泊晴(2010)，人工智慧最佳化於警車巡邏問題之研究，虎尾　　 科技大學工業管理系研究所，碩士論文[19] 張永泰(2007)，應用於系統晶片設計之有效避免障礙物的直角化最小史坦那樹建構演算法，中原大學資訊工程學系，碩士論　　 文[20] 蔡崑佑(2009)，警察巡邏路線之研究，朝陽科技大學建築及都　　 市設計研究所，碩士論文[21] 廖逸芳(2007)，考慮貨物擺設及行經特定點之收送或圖程問　　　 題，國立東華大學全球運籌管理研究所，碩士論文[22] 維基百科，曼哈頓距離http://zh.wikipedia.org/wiki/%E6%9B%BC%E5%93%88%E9%A0%93%E8%B7%9D%E9%9B%A2[23] 鄧宗倫(2009)，應用人工智慧法於最佳消毒作業之十時窗限制　　 車輛途程問題，虎尾科技大學工業管理研究所，碩士論文[24] 蕭小林(2008)，彰化縣警察巡邏勤務之政策研究，逢甲大學公　　 共政策研究所，碩士論文[25] 盧尚群(2005)，依時路網車輛路徑規劃系統，國立高雄第一科　　 技大學運籌管理系，碩士論文[26] 戴昌亮(2005)，考量訊號延遲即可繞度之多湊繞線系統，私立　　 中原大學資訊工程學系，碩士論文[27] 警察勤務條務http://www.6law.idv.tw/6law/law/%E8%AD%A6%E5%AF%9F%E5%8B%A4%E5%8B%99%E6%A2%9D%E4%BE%8B.htm[28] D. Villeneuve & G. Desaulniers (2005). “The shortest　　　 path problem with forbidden paths”,European Journal　　 of Operational Research,Vol. 165, pp.97–107.[29] Ibaraki, T. & Kubo, M. & Masuda, T. & Uno, T. &Yagiurs, M. (2001).“Effective local search algorithmsfor the vehicle routing problem with general timewindows,” Working paper, Department of AppliedMathematics and Physics, Kyoto University, Japan.[30] L. Bodin & B. L. Golden & A. Assad& M. Ball (1983),“Routing and Scheduling of Vehicle and Crew: The　　 State of Art”, Special Issue of Computers&　　 Operations Research 10:2, pp.63-211,[31] Li, H. and Lim, A., “A Metaheuristic for the Pickup 　　　 and Delivery Problem with Time Windows,” 13th IEEE　　　 International Conference on Tools with Artificial　　 Intelligence (ICTAI’01), Pages: 160-167, 7-9 Nov.2001.[32] P. M. Thompson, H. Psaraftis, “Cyclic TransferAlgorithms for Multi-Vehicle Routing and SchedulingProblems”, Operations Research, Vol.41, 935-946, 1993.[33] P. M. Thompson & H. Psaraftis (1993). “Cyclic　　 Transfer Algorithms for Multi-Vehicle Routing &　　 Scheduling Problems”, Operations Research, Vol.41,　　 pp.935-946.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 應用人工智慧法於最佳消毒作業之時窗限制車輛途程問題 2 彰化縣警察巡邏勤務之政策研究 3 依時路網車輛路徑規劃系統 4 警察巡邏路線之研究 5 考慮貨物擺設及行經特定點之收送貨途程問題 6 正交系統中不連續線段之最短路徑之研究 7 警察巡邏路線規劃模式暨求解演算法之研究

 1 [58]朱國瑞(2006年4月)，高壓線、微波爐及電磁武器Q&A，物理雙月刊，第28卷，第2期，505-509頁。 2 [58]朱國瑞(2006年4月)，高壓線、微波爐及電磁武器Q&A，物理雙月刊，第28卷，第2期，505-509頁。 3 [4]洪炳南(1983年，11月)，生物材料在醫學上的應用，科學月刊，第167期。 4 [4]洪炳南(1983年，11月)，生物材料在醫學上的應用，科學月刊，第167期。

 1 正交系統中不連續線段之最短路徑之研究 2 以具分散反萃取相支撐式液態薄膜分離並回收廢螢光粉內釔離子之研究 3 製備摻氮氧化鋅聚偏氟乙烯薄膜進行可見光催化之研究 4 以科技接受模式探討國中教師以數位學習在職進修之意向之研究 5 泰國糖類輸出之因素分析 6 以移動平均線法研究台灣股市 7 影響YouBike騎乘行為之研究 8 都市中自然音景與交通噪音對焦慮情緒之影響 9 應用基因演算法於批次排程 10 整合厭氧生物處理之低耗能廢水再生系統 11 網格網路中最短漢米爾頓路徑之研究 12 日治時期臺灣「亞洲型霍亂」之研究(1895-1945) 13 新豐鄉姜厝(朴樹林)多脊沙丘聚落生活地景之探討 14 探討文化創意產業人才所需之關鍵核心能力-以鶯歌陶瓷產業為例 15 撞期決策與消費者選擇－電影上映日期與票房分析

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