淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1206200814133700
中文論文名稱 以演化基礎的塔布搜尋方法解旅行銷售員問題
英文論文名稱 Evolution-Based Tabu Search Approach to Traveling Salesman Problem
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 96
學期 2
出版年 97
研究生中文姓名 張震宇
研究生英文姓名 Chen-Yu Chang
學號 695630631
學位類別 碩士
語文別 中文
口試日期 2008-05-24
論文頁數 47頁
口試委員 指導教授-李鴻璋
委員-侯永昌
委員-梁恩輝
委員-呂芳懌
委員-吳瑞堯
中文關鍵字 旅行銷售員問題  基因演算法  塔布搜尋法 
英文關鍵字 Traveling Salesman Problem  Genetic Algorithm  Tabu Search 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 組合最佳化問題中,旅行銷售員問題(Traveling Salesman Problem, TSP)是最基本且典型的例子,許多問題都可以轉變成TSP的形式求解,又由於TSP是屬於NP-Complete問題,在資料量龐大的情況之下無法找出最佳解,所以又有將大型TSP變換成數個小型TSP的分群旅行銷售員問題(Clustered Traveling Salesman Problem, CTSP)的研究提出。所以,如何設計一個良好的演算法,使得我們能夠能找出近似最佳解變得相當重要。因此,本研究提出以基因演算法及塔布搜尋法為核心的演算架構,並將TSP問題轉為CTSP問題型式,以期能找出近似最佳解。
本研究所提出的演算架構分為二個部分,第一部分為分群及群路建立,第二部分為全域最佳路徑搜尋。分群為階層式,由上而下分群,首先將頂點做初步分群,完成後再將每一群分為若干子群並建立群路路徑。第二部分的全域最佳路徑,搜尋方法採用塔布搜尋法,首先使用雙點式塔布搜尋做大範圍的路徑搜尋,接著使用單點式塔布搜尋做細部改善,最後使用MNIO演算法將解收斂。在TSPLIB國際範例korA100中,基因演算法所得的路徑長度比最佳解長5.27%,本研究只多出2.46%;在d198中,基因演算法的路徑長度比最佳解多出5.96%,本研究只多出3.44%;而在rat783中,基因演算法的路徑長度比最佳解多出10.52%,本研究只多出8.72%。因此可以看出,本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
英文摘要 In the combinatorial optimization problem, Traveling Salesman Problem is the most basic and typical example, lots of problems could transfer to TSP as solution. Meanwhile, as the TSP belongs to NP-Complete problem, it is quite hard to find out the best solution in case of huge data, the CTSP, Clustered Traveling Salesman Problem, transferred from a big TSP into several smaller ones, came up. Therefore, it becomes highly important to define a good algorithm in order to find the best similar solution. In consequence, this research proposes an algorithm; the cadre is based on genetic algorithm and tabu search, and transfer the TSP problem into CTSP to find out the best similar solution.
In this research, the algorithm is divided into two parts: the first one on the cluster path, second on the global best path search. The cluster is top- down; at the beginning making the preliminary cluster on the top, then set up the path. The second part, adopting the tabu search: firstly by using the two-points tabu search as large boundary, then by one point tabu search for detail, finally by using MNIO algorithm for the final solution. In TSPLIB international exemplification linkorA100, the path of genetic algorithm is 5.27% longer than the best solution, in this research only 2.46% longer; in the d198, the path of genetic algorithm is 5.96% longer than the best solution, in this research 3.44% only; as for the rat783, the path of genetic algorithm is 10.52% longer than the best solution, here only longer than 8.72%. Therefore, the algorithm of this research can get a better path research result than by using uniquely the genetic algorithm.
論文目次 目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
第二章 文獻探討 3
2.1 旅行銷售員問題(Traveling Salesman Problem) 4
2.2 分群旅行銷售員問題(Clustered Traveling Salesman Problem) 6
2.3 K-means演算法 6
2.4 塔布搜尋法 10
2.5 基因演算法 14
2.5.1 編碼 16
2.5.2 複製 17
2.5.3 交配 18
2.5.4 突變 21
2.6 CGS演算法 22
2.6.1 分群 23
2.6.2 全域最佳化 24
第三章 演算法架構及說明 27
3.1 分群及群路建立 29
3.1.1 K-means演算法 29
3.1.2 基因演算法 30
3.1.3 clusterTSP 31
3.2 全域最佳路徑搜尋 31
3.2.1 雙點式塔布搜尋 31
3.2.2 單點式塔布搜尋 31
3.2.3 MNIO (Multiple Neighborhood Inversion Operator) 32
第四章 實驗結果 33
第五章 結論 43
參考文獻 44


圖目錄
圖1 k-means原始資料圖 8
圖2 k-means演算法步驟1 8
圖3 k-means演算法步驟2 9
圖4 k-means演算法步驟3 9
圖5 k-means演算法步驟4 10
圖6 塔布搜尋法流程圖 13
圖7基因演算法流程圖 15
圖8基因編碼型態 17
圖9 輪盤法 17
圖10 單點交配 19
圖11 雙點交配 19
圖12 順序交配 20
圖13 字罩交配 21
圖14 突變 22
圖15 CGS流程圖 22
圖16 WEIO (資料來源:A Clustering and Genetic Scheme for Large TSP Optimization Problems) 25
圖17 演算法架構 27
圖18 路徑搜尋流程圖 29
圖19 染色體編碼 30
圖20 基因母體數量與路徑變化關係 34
圖21 塔布候選清單大小與路徑長短關係 35
圖22 單點塔布搜尋 35
圖23 MNIO 36

表目錄
表1 fl417參數設定 36
表2母體個數與路徑長度 37
表3基因演算法迭代數與路徑長度 38
表4塔布候選清單大小與路徑長度 38
表5 塔布迭代數與路徑長度 39
表6 MNIO迭代數與路徑長度 39
表7各階段路徑長度改善情況 41
表8本研究與GA演算法比較 41
表9本研究與CGS演算法比較 42

參考文獻 參考文獻
[1]Bodin, L., Golden, B., Assad, A. and Ball M. Routing and Scheduling of Vehicle and Crews. The state of the art, Computers and Operations Research, 10(2), p63-p211, 1983.
[2]Chien-Ying Lu, Jose G. Delgado-Frias, Wei Lin, “A Clustering and Genetic Scheme for Large TSP Optimization Problems”, Cybernetics and Systems, Vol.29, No.2 p137-p157 ,March 1998.
[3]Dantzig, G.B., Fulkerson, D.R. and Johnson S.M., “Solution of a large-scale Traveling Salesman problem”, Operations Research, 2(4), p393-p410,1954
[4]David, B., David, R. B., Ralph, R. M., “An Overview of Genetic Algorithms, Part1, Fundamentals”, University Computing, Vol. 15, No. 2, p58-p69, 1993.
[5]David, B., David, R. B., Ralph, R. M., “An Overview of Genetic Algorithms, Part2, Research Topics”, University Computing, Vol. 15, No. 4, p170-p181, 1993.
[6]Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a search strategy”, Technical Report 91-016, Dipartimento Elettronica, Politecnico di Milano, Italy, 1992.
[7]Dorigo, M., “Optimization learning and natural algorithms”, PhD Thesis, Dip. Elettronica, Politecnico di Milano, Italy, 1992.
[8]Dorigo, M., Maniezzo, V. and Colorni, A. “Ant system : Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26(1), p29-p41.,1996.
[9]Dueck, G. and Scheuer, T., “Threshold accepting:A general purpose optimization algorithm appearing superior to simulated annealing”, Journal of Computational Physics, Vol. 90, p161-p175, 1990.
[10]F.C.J.Lokin. “Procedure for traveling salesman problems with additional constraints”, European Journal of Operational Research, 3:p135-p141, 1978.
[11]Flood, M., “The Traveling Salesman Problem”, Operations Research, 4, p61-p75,1956.
[12]Glover, F. and M. Laguna, “Tabu Search, Blackwell Scientific Publications”, Oxford, 1993.
[13]J.A. Chisman. “clustered traveling salesman problem”, Computers and Operations Research, 2:p115-p119,1975.
[14]MacQueen, J.B. “Some Methods for Classification and Analysis of Multivariate Observations”, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, p281-p297, 1967.
[15]Karp, R., “Reducibility among Combinatorial Problems”, Complexity of Computer Computations, Plenum Press, p85-p104,1972.
[16]Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P. , ”Optimization by simulated annealing”, Science, Vol.220,p671-p680,1983.
[17]Larranaga, P., Kuijpers, C. M. H.,Murga, R. H., Inza, I., Dizdarevic, S. “Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators”, Artificial Intelligence Review. 13, p129-p170,1999.
[18]L. Fiechter, “A parallel Tabu search algorithm for large traveling salesman problems”, Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, vol. 51, p243-p267, 1994.
[19]Michalewicz, Z. 1992. “Genetic algorithms + data structures = evolution programs”, New York: Springer-Verlag.
[20]Rosenkrantz, D.J., Streans, R.E. and Lewis, P. N. An analysis of Several Heuristics for the Traveling Salesman Problem, SLAM Journal on Computing, 6,p563-p58,1977.
[21]Shubhra Sankar Ray, Sanghamitra Bandyopadhyay and Sankar K. Pal, ” New Genetic Operators for Solving TSP: Application to Microarray Gene Ordering”, Vol. 3776,p617-p622,1995.
[22]TSPLIB Homepage:
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-06-18公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-06-18起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信