臺灣博碩士論文加值系統

現今各個產業為減少生產成本以及其生產品質的不確定性，其生產人力已逐漸淘汰，改變以自動化生產設備替代，各種產業的工業製程皆都逐漸邁向完全自動化的階段，其中更以大量生產為主的高科技產業最為顯著，因此，為自動化生產製程做其生產路徑的規劃，將會是一個重要的問題，而本研究將提出一個演算方法來解決在網格網路中有多個必經節點並搜尋其最短之漢米爾頓路徑，其演算步驟為:(1)將其各個目標點整理出目標與目標之間的最短路徑並以矩陣方式排列。(2)將該矩陣以指派方法為其各目標之間作指派。(3)指派結果為一起的各個目標點將形成迴圈，將各個迴圈當中距離為最大的一條連結刪除形成路徑，並且使其各個路徑成為新目標。(4)重複步驟(1)、(2)、(3)，直到degree數為1的節點數為2，則結束運算，得出一個能連結所有節點的漢米爾頓路徑。(5)針對上述演算得出的漢米爾頓路徑，以N型與Z型概念來對該結果當中的路徑做其修正。本研究是以指派問題的求解方式來做為搜尋路徑的主要方法，由於指派問題的特性，是使該分配結果的成本或是效益能夠達到最佳化，因此能保證其指派連結的結果為最短，但由於在本研究的演算方法過程中，存在著一個有著不確定性的運算動作，也因此，該演算的運算結果將無法保證其為最佳解，故本研究後續又提出了一個修正方法，該修正方法是以上述搜尋方法求出的結果為基礎，以N型與Z型概念來對該結果當中的路徑做其修正，使得本研究能夠在網格網路當中，找出一條最短漢米爾頓路徑之逼近解。

In order to reduce the production cost and uncertainty, automation will gradually replace human in the future, especially in high-tech industry. The planning of production path that offers least cost is a critical issue for automatic production process. To solve the production path problem, a new algorithm is proposed in this research. The basic characteristic of the proposed algorithm is to solve a Hamiltonian path along a set of given points on a grid graph that has only horizontal and vertical freedom. The proposed algorithm includes the following major steps: (1) Find the shortest path among the target points and set the corresponding distance values to a matrix. (2) Solve the matrix obtained from step (1) by using the assignment algorithm. The computation result of this step is one or more cycles. (3) Remove the longest edge from the cycles of step (2) and combine the corresponding edges into one single path. (4) Repeat steps (1) to (3) until only two given points get one degree. (5) Modify the Hamiltonian path based on the proposed algorithm. The Hamiltonian path is an NP-problem. It is very difficult to find an exact optimum solution. To reach a better approximation solution, N-type and Z-type paths are proposed in this research to help the modification of the computation.

目錄

摘要.....................................................i
Abstract............................................... ii
誌謝....................................................iii
目錄.................................................... iv
圖目錄.....................................................v
第一章緒論.....................................................1
1.1 研究背景.....................................................1
1.2 研究目的.....................................................1
1.3 研究流程.....................................................2
1.4 論文架構.....................................................3
第二章 相關文獻探討.....................................................4
2.1 前言.....................................................4
2.2 圖網理論.....................................................4
2.3 漢米爾頓問題.....................................................4
2.4 歐拉路徑.....................................................4
2.5 曼哈頓距離.....................................................5
2.6 匈牙利法.....................................................5
2.7 最短路徑問題.....................................................7
2.8 戴式演算法.....................................................8
第三章 研究方法.....................................................9
3.1 想法構思.....................................................9
3.2 正交直角特性.....................................................10
3.3 搜尋方法.....................................................10
3.4 搜尋步驟.....................................................11
3.5 修正方法.....................................................15
第四章 實驗與討論.....................................................18
4.1 範例討論.....................................................18
4.2 演算前置操作.....................................................19
4.3 演算方法及操作步驟.....................................................21
4.4 路徑修正.....................................................31
4.5 結果與討論.....................................................36
第五章 結論.....................................................38
參考文獻.....................................................39

圖目錄

圖1.1 研究流程架構圖.....................................................2
圖1.2 論文架構圖.....................................................3
圖2.1匈牙利法運算之範例.....................................................5
圖2.2各列找最小值並減去.....................................................6
圖2.3各行找最小值並減去.....................................................6
圖2.4檢驗是否可以作指派.....................................................6
圖2.5以最少數目劃出刪除線並包含所有的零.....................................................7
圖2.6將有未被劃線的元素各列減去最小K值.....................................................7
圖3.1迴圈路徑及漢米爾頓路徑.....................................................9
圖3.2沿著網格路徑行走及不可行路徑.....................................................10
圖3.3網格上點之位置各個節點到節點間的最短距離矩陣.....................................................11
圖3.4將網格網路圖上的最短距離整理並以矩陣表示.....................................................12
圖3.5以99來取代各點與本身的最短距離數據.....................................................12
圖3.6作指派分配.....................................................13
圖3.7指派結果為2個以上的迴圈產生.....................................................13
圖3.8將各迴圈路徑最大的edge刪除並視其為集合.....................................................14
圖3.9 整理各個集合.....................................................14
圖3.10將集合間做配對形成迴圈.....................................................15
圖3.11以degree數不為2的兩節點分別使其為起點及終點.....................................................16
圖3.12路徑1、2、3、4.....................................................17
圖4.1亂數選出node位置.....................................................18
圖4.2各node之間距離矩陣.....................................................19
圖4.3各node之距離矩陣修正後.....................................................20
圖4.4以最佳化建模軟體AIMMS的數學模型以及其目標函數.....................................................22
圖4.5將各Node作指派分配並做連結.....................................................23
圖4.6刪除edge最大的一連結.....................................................24
圖4.7整理出各集合中degree數不為2的節點的最短距離.....................................................25
圖4.8整理出各集合間的最短距離矩陣.....................................................25
圖4.9將各集合作指派分配並做連結.....................................................26
圖4.10刪除edge最大的一連結.....................................................27
圖4.11整理出各集合中degree數不為2的節點的最短距離.....................................................28
圖4.12整理出各集合間的最短距離矩陣.....................................................28
圖4.13將各集合作指派分配.....................................................29
圖4.14將各集合做連結.....................................................29
圖4.15刪除edge最大的一連結.....................................................30
圖4.16最後完成.....................................................31
圖4.17將degree數不為2的兩點設為起點和終點並依序排列.....................................................32
圖4.18各node之間距離矩陣.....................................................33
圖4.19原路徑被取代為新路徑並重新命名.....................................................34
圖4.20原路徑取代為新路徑並重新命名.....................................................35
圖4.21完成路徑.....................................................36

吳瑞瑜，(2001)，金字塔網路之漢彌爾頓性質，國立暨南國際大學資訊工程學系，碩士論文。
2.宋占奎，(2009)，Assignment Problem匈牙利法研討，陝西教育學院學報，第二十五卷，第二期，93-96頁。
3.卓哲強，(2006)，網路線性之最短路徑問題，虎尾科技大學虎尾科技大學工業工程與管理研究所學位論文，碩士論文。
4.陳思齊，(2007)，巡邏車輛途程問題，中央大學中央大學土木工程學系學位論文，碩士論文。
5.葉羿稚，(2007)，行前即時路徑規劃演算法之研究，臺灣大學土木工程學研究所，碩士論文。
6.謝逢鳴，(2004)，有前處理下最短路徑演算法之研究，淡江大學資訊管理學系碩士班，碩士論文。
7.Ibaraki, T., Kubo, M., Masuda, T., Uno, T., and Yagiurs, M. (2001), “Effective local search algorithms for the vehicle routing problem with general time windows”, Department of Applied Mathematics and Physics, Vol.2001, pp.293-297.
8.Li, H. and Lim, A. (2003), “A Metaheuristic for the Pickup and Delivery Problem with Time Windows”, International Journal on Artificial Intelligence Tools, Vol.12, No.02, pp.173-186.
9.P. M. Thompson, H. Psaraftis (1993), “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems”, Operations Research, Vol.41, No.5 , pp.935-946.
10.Raff, S. (1983), “Routing and Scheduling of Vehicle and Crew: The State of Art”, Special Issue of Computers and Operations Research, Vol.10, No.2, pp.63-211.
11.Denardo, E. V. and Fox, B. L. (1979), “Shortest-route methods: 1. Reaching, pruning, and buckets. ” Operations Research, Vol.27, No.1, pp.161-186.
12.Cherkassky, B. V., Goldberg, A. V. and Radzik, T. (1996), “Shortest paths algorithms: Theory and experimental evaluation”, Mathematical Programming, Vol.73, No.2, pp.129-174.
13.Bertsekas, D. P. (1991), “Linear network optimization: algorithms and codes”, MIT Press.
14.Van Vliet, D. (1978), “Improved shortest path algorithms for transport networks”, Transportation Research, Vol.12, No.1, pp.7-20.