- 學位論文
正交系統中不連續線段之最短路徑之研究
The Study of Minimum Routing Around Disconnected line Segments under Rectangular System
摘要
近年來，路徑途程問題被廣泛運用在各個研究領域，而路徑問題中以最短路徑為其核心問題所在，而本研究主要是探討在不連續型線段之最短路徑問題，而此問題常廣泛的應用於一般生活當中，如警察於一般道路巡邏問題、郵差送信、自動倉儲搬運車、自動化機械手臂加工等。 在以往的文獻中都屬於連續型之最短路徑研究，常以兩點之間最短距離作為連接線段，忽略掉連結路徑上可能會碰觸到障礙物等，而並未加以考量實際路徑上的狀態，如限制必行路徑、遇到不連續型之線段等，綜合以上之問題，本論文針對上述問題，提出了一個在不連續型線段裡搜尋最短重覆路徑的新演算法，在圖形為不連續型線段中，且在必行路徑裡，應用直角坐標演算法來連結所有不連續型線段，利用圖形中的端點(vertex)自由度(degree)來判定是否成為重覆路徑的主要因素，也運用新的演算法來實際套用在不連續型路徑圖中，經由實驗中的不同起始點和連接路徑相互比較之下，在不連續型路徑裡找到了最短重覆路徑的逼近解。
並列摘要
The path routing technique is extensively used in various areas. The minimum routing problem is one of the important topics of the path routing problems. The essence of this research is to study the minimum routing length around disconnected line segments under rectangular system that is widely used in areas like Police Patrol Routs Problem, Postman Problem, Automated Warehousing Handling System and Automated Robotic Arm Process. Most of the previous studies are concentrated in the area of minimum routing problems of connected line segments. The problems about obstacle objects, forbidden paths or minimum path around disconnected line segments are often ignored. To solve the routing problem around disconnected line segments, a new algorithm is proposed in this research. The basic idea of the proposed algorithm is to keep the degree of all intermediate vertices as an even number under the constraint that the total length of the repeated line segments is as short as possible. Finally, comparison of different situations is presented.