正交網格網路之不連續線段的重複路徑研究

本文主要是探討最短路徑問題，是求在平面上找出指定的節點間之最短連接線段，以供做為各領域之路徑使用，現今，最短路徑的求解方法有許多種，但並不能準確的建構出真正的最短路徑，因此有許多學者嘗試求解出較佳的近似解，以供各領域參考。一般研究所探討的最短路徑問題，其各節點所連接的路徑，皆為連續型線段，此方法卻並未加以考量路徑限制問題，如:障礙物、限制路徑等問題，這些問題使得線段成現不連續型線段，並增加演算過程的複雜化，因而衍生出將實際路徑結合網格圖(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.

並列關鍵字

Shortest routing ； Vehicle Routing Problem ； Police Patrol Routes

參考文獻

政策略探討，銘傳大學社會科學院國家發展與兩岸關係碩士在

[11] 許晉嘉(2003)，宅配業或物配送路線規劃問題之研究，國立成

[4] 林育甫(2006)，利用K條最短路徑預測為新成之代謝途徑，國立

[6] 林家慶(2008)，在實踐限制下有效率地探勘前K條最短路徑，國

[15] 陳思齊(2007)，巡邏車輛途程問題，國立中央大學土木工程學

國際替代計量

正交網格網路之不連續線段的重複路徑研究

未授權

主題瀏覽