組合最佳化問題中，旅行銷售員問題(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/