(3.236.222.124) 您好!臺灣時間:2021/05/11 09:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:崔世選
研究生(外文):Shih-Shiuan Tsui
論文名稱:正交網格網路之不連續線段的重複路徑研究
論文名稱(外文):The Study of Repeat Routing Around Disconnected Line Segments under Rectangular Mesh Networking System
指導教授:黃俊平黃俊平引用關係
指導教授(外文):Jyun-Ping Huang
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:工業工程與管理研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:80
中文關鍵詞:最短路徑問題車輛途程問題警察巡邏路徑
外文關鍵詞:Shortest routingVehicle Routing ProblemPolice Patrol Routes
相關次數:
  • 被引用被引用: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.


中文摘要 ---------------------------------------------- i
Abstract --------------------------------------------- ii
誌謝 ---------------------------------------------- iii
目錄 ---------------------------------------------- iv
表目錄 ---------------------------------------------- vi
圖目錄 ---------------------------------------------- vii
第一章 緒論------------------------------------------ 1
1.1 研究背景-------------------------------------- 1
1.2 研究目的-------------------------------------- 2
1.3 研究條件限制---------------------------------- 2
1.4 研究方法與步驟-------------------------------- 3
第二章 相關文獻探討---------------------------------- 6
2.1 前言------------------------------------------ 6
2.2 警察巡邏勤務---------------------------------- 6
2.2.1 巡邏勤務定義---------------------------------- 7
2.2.2 巡邏勤務目的---------------------------------- 8
2.2.3 巡邏勤務內容---------------------------------- 9
2.2.4 巡邏勤務的方式-------------------------------- 10
2.2.5 警察巡邏相關研究------------------------------ 12
2.3 中國郵差問題---------------------------------- 13
2.3.1 中國郵差問題的求解策略------------------------ 14
2.4 車輛途程問題---------------------------------- 15
2.4.1 車輛途程問題的求解策略------------------------ 16
2.5 最短路徑問題---------------------------------- 18
2.5.1 K條最短路徑問題------------------------------- 20
2.5.2 禁止路徑問題---------------------------------- 22
第三章 研究方法-------------------------------------- 23
3.1 名詞解釋與定義-------------------------------- 23
3.2 問題說明-------------------------------------- 26
3.2.1 演算法流程------------------------------------ 30
3.3 建立Raster graphics--------------------------- 31
3.3.1 曼哈頓距離(Manhattan distance)---------------- 32
3.4 可行路徑的建構-------------------------------- 33
3.4.1 可行路徑的修正-------------------------------- 36
3.5 重複路徑演算法-------------------------------- 38
3.6 交疊線段-------------------------------------- 44
3.6.1 正交四邊形繞法-------------------------------- 45
3.6.2 正交重覆路徑走法------------------------------ 48
3.6.3 正交重複路徑走法與正交四邊形繞法的比較與應用-- 50
3.7 不規則線段------------------------------------ 51
3.7.1 不規則線段的重複路徑建構---------------------- 56
3.7.2 不規則交疊線段的重複路徑走法------------------ 56
3.8 研究方法彙整---------------------------------- 57
第四章 實驗與討論------------------------------------ 60
4.1 實驗介紹-------------------------------------- 60
4.1.1 路徑圖的建構---------------------------------- 61
4.1.2 路徑圖的可行路徑建構-------------------------- 62
4.1.3 可行路徑的線段修正---------------------------- 64
4.1.4 最短重複路徑圖-------------------------------- 66
4.2 不同起、終點之研究---------------------------- 67
4.3 最短重複路徑問題比較-------------------------- 68
4.4 討論總結-------------------------------------- 70
第五章 結論與未來發展-------------------------------- 71
5.1 結論------------------------------------------ 71
5.2 未來與展望------------------------------------ 72
文獻參考 ---------------------------------------------- 73
Extended 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%9
3%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 algorithms
for the vehicle routing problem with general time
windows,” Working paper, Department of Applied
Mathematics 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 Transfer
Algorithms for Multi-Vehicle Routing and Scheduling
Problems”, 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.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔