旅行銷售員問題(Travelling Salesman Problems, TSP)為模擬推銷員送貨模式並求解最佳路徑之典型最佳化問題。且已被證明為NP-complete的問題，由於複雜度較高，有時無法於短時程求得最佳解，故一般常以啟發式方法(heuristic method)求取近似最佳解。由於以啟發式解法求算旅行銷售員問題時，若運算之規模愈大其求解時間亦會隨節點數遞增而呈指數成長。因此，研究學者利用生物之特性，提出數種著名巨集啟發式解法來改善此問題。其中，基因演算法為一種巨集啟發式解法，且已被廣泛應用於組合最佳化問題中。本研究以典型基因演算法為基礎架構，建立一並聯運算機制，藉此改善其求解之效能。於實驗結果可得，本研究所提出之多元基因演算法(Pluralistic Genetic Algorithm, PGA)與各式演算法相互比較之結果，皆具較佳之表現且易於進行參數之設置，因此，多元基因演算法對於求解旅行銷售員問題具良好之求解品質。

The travelling salesman problem (TSP) is a benchmark problem in which a salesman has to visit all nodes (cities) in a network exactly once except the starting node, coming back to the starting node and find the shortest tour. Genetic algorithm (GA) is one of the best algorithms to deal with the travelling salesman problem (TSP). In GA, crossover and mutation operator play a vital role, and several improvements have been proposed for these operators. In this paper, we show how using a new approach for the quality of the solutions is improved. We propose Pluralistic Genetic Algorithm (PGA ) using five local search methods – OX1, 2-opt search, and three basic mutation operators, then incorporate them with a parallel connection. The experimental results on some TSPLIB instances show that our PGA is more efficient than other traditional population based on algorithms, such as genetic algorithm, particle swarm optimization, artificial immune system, and so on.

[1] 吳泰熙、張欽智(1997)，「以禁忌搜尋法則求解推銷員旅行問題」，　 大葉大學學報，6(1)，87-99。
[2] 林昇甫、徐永吉(2009)，「遺傳演算法及其應用」，五南圖書出版公司，1-5。
[3] 林家富、劉宏毅、蔡金橤、郭東義(2010)，「含菁英政策之基因演算法於模式最佳化近似的應用」，工程科技與教育學刊，7(3)，437- 444。
[4] 許為元(2000)，「複合式自我學習之基因演算法應用於旅行推銷員問題」，國立台灣大學資訊工程研究所碩士學位論文。
[5] 陳建緯(2001)，「大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用」，國立交通大學運輸工程與管理學系碩士學位論文。
[6] 陳柏志(2012)，「以礦工基因演算法求解旅行商問題」，國立臺灣科技大學工業管理系碩士學位論文。
[7] 曾郁展(2005)，「DSP-Based之即時人臉辨識系統」，國立中山大學電機系碩士學位論文。
[8] 韓復華、卓裕仁(1999)，「網路節點服務TSP與VRP問題回顧。運輸網路分析」，五南圖書出版公司，8，201-223。
[9] 韓復華、張靖、卓裕仁(1996)，「車輛路線問題研究：SA、TANMSSS與交換型啟發式方法之綜合應用分析」，運輸學刊，9(3)，103-129。
[10] 韓復華、楊智凱(1996)，「門檻接受法在TSP問題上之應用」，運輸計劃季刊，25(2)，163-188。
[11] Baker, B.M. and Ayechew, M.A., (2003), “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, 30, 787-800.
[12] Bellmore, M. and Nemhauser, G.L., (1968), “The Traveling Salesman Problem: A Survey,” Operations Research, 16(3), 538-558.
[13] Bodin, L., Golden, B., Assad, A. and Ball, M., (1983), “Routing and Scheduling of Vehicle and Crews,” The state of the art, Computers and Operations Research, 10(2), 63-211.
[14] Chakroborty, P. and Mandal, A., (2005), “An asexual genetic algorithm for the general single vehicle routing problem,” Engineering Optimization, 37(3), 1-27.
[15] Chatterjee, S., Carrera, C. and Lynch, L.A., (1996), “Genetic algorithm and traveling salesman problems,” European Journal of operational research, 93, 490-510.
[16] Chen, H., Li, S. and Tang, Z., (2011), “Hybrid Gravitational Search Algorithm with Random-key Encoding Scheme Combined with Simulated Annealing,” International Journal of Computer Science and Network Security, 11, 208-217.
[17] Cheng, T.C.E. and Wang, G., (2000), “Single Machine Scheduling with Learning Effect Considerations,” Annals of Operation Research, 98, 273-290.
[18] Choi, I., Kim, S. and Kim, H., (2003), “A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem,” Computers & Operations Research, 30, 773-786.
[19] Clarke, G. and Wright, J.W., (1964), “Scheduling of Vehicles from A Central Depot to A Number of Delivery Points,” Operations Research, 12(4), 568-581.
[20] Croes, G.A., (1958), “A Method for Solving Traveling Salesman Problems,” Operations Research, 6(6), 791-812.
[21] Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M., (1954), “Solution for a Large-Scale Traveling Salesman Problem,” Journal of Operatoins Research Society of America, 2, 393-410.
[22] Deep, K. and Mebrahtu, H., (2011), “New Variations of Order Crossover for Travelling Salesman Problem,” International Journal of Combinatorial Optimization Problems and Informatics, 2(1), 2-13.
[23] Dorigo, M. and Gambardellam, L.M., (1997), “Ant colony system: a cooperative learning approach to the travelling salesman problem,” IEEE Transactions Evolutionary Computation, 1, 53-66.
[24] Dorigo, M., Caro, G.D. and Gambardella, L.M., (1999), “Ant algorithms for distributed discrete optimization,” Artificial Life, 5, 137-172.
[25] Dorigo, M., Maniezzo, V. and Colorni, A., (1996), “Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 29-41.
[26] Dueck, G. and Scheuer, T., (1990), “Threshold accepting: a general purpose optimization algorithm appeared superior simulated annealing,” Journal of Computational Physics, 90, 161-175.
[27] Flood, M.M., (1956), “The Travelling Salesman Problem,” Operations Research, 4, 61-75.
[28] Glover, F., (1989), “Tabu search—part I,” ORSA Journal on Computing, 1(3), 190-206.
[29] Glover, F., (1990), “Tabu search—part II,” ORSA Journal on Computing, 2(1), 4-32.
[30] Goldberg, L. R., (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.
[31] Holland, J.H., (1975), “Adaptation in Natural and Artificial Systems,” Ann Arbor, MI: Univ, Michigan Press.
[32] Karp, R., (1972), “Reducibility among Combinatorial Problem,” Complexity of Computer Computations, 85-104.
[33] Kirkpartrick, S., Gelatt, C.D. and Vecchi, M.P., (1983), “Optimization by simulated annealing,” Science, 220, 671-680.
[34] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., (1985), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley and Sons, New York.
[35] Lin, S. and Kernighan, B.W., (1973), “An Effective Heuristic Algorithm for the Travelling Salesman Problem,” Operations Research, 21, 498-516.
[36] Lin, S., (1965), “Computer solutions of the traveling salesman problem,” The Bell System Technical Journal, 2245-2269.
[37] Michalewicz, Z., (1996), Genetic algorithm + data structures = evolution programs, Third, Revised and Extended, Springer.
[38] Or, I., (1976), Travelling salesman-type Combinatorial Problems and Their relation to the Logistics of Regional Blood Banking, ph.D. Dissertation. Northwestern University, Evanston, IL.
[39] Pattnaik, S.B., Mohan, S. and Tom, V.M., (1998), “Urban bus transit route network design using genetic algorithm,” Journal of transportation engineering, 368-375.
[40] Poon, K.F., Conway, A., Wardrop, G. and Mellis, J., (2000), “Successful application of genetic algorithms to network design and planning,” BT Technology Journal, 18(4), 32-40.
[41] Puris A., Bello R. and Herrera F., (2010), “Analysis of the efficacy of a Two-Stage methodology for ant colony optimization: Case of study with TSP and QAP,” Expert Systems with Applications, 37, 5443-5453.
[42] Reeves, C.R., (1993), Modern heuristic techniques for combinational problems, New York: Halsted Press, Chapter 4.
[43] Rosenkrantz, D.J., Streans, R.E. and Lewis, P.N., (1977), “An analysis of Several Heuristics for the Traveling Salesman Problem,” SLAM Journal on Computing, 6, 563-581.
[44] Sena, G.A., Megherbi, D. and Isern, G., (2001), “Implementation of a parallel Genetic Algorithm on a cluster of workstations:Traveling Salesman Problem,a case study,” Future Generation Computer Systems, 17, 477-488.
[45] Singh, S. and Lodhi E.A., (2013), “Study of Variation in TSP using Genetic Algorithm and Its Operator Comparison,” International Journal of Soft Computing and Engineering, 3, 2.
[46] Wetzel, R.G., (1983), Limnology, 2nd Edition, Saunders College Publishing, Philadelphia, PA.