推銷員旅行問題(Traveling Salesman Problem, TSP)是一種模擬推銷員送貨模式的一種最佳化問題(Optimization Problems)，此問題定義為一個推銷員從起始城市出發，必須拜訪所有城市，最後再回到出發的城市，求所需的總時間或是總成本最小，目前已被證明為NP-hard 問題，而解決此種最佳化問題，傳統以貪婪式演算法(Greedy Method)在每一步都選擇當前狀態最好的，而後再以鄰近交換法(Neighborhood Exchange)或局部搜尋法(Local Search)進行改善，然而此種方式會容易收斂在局部區域解，而無法保證找到最佳解，因此我們使用啟發式演算法這類模仿生物演化行為特性的演算法，擁有較高彈性，較不容易落到區域最佳解裡面。

而本研究所提出之基因演算法及蟻群演算法正是屬於啟發式演算法，利用基因演算法做整體演算法架構，並且利用三交叉交配的法則來求得初始最佳解，再利用蟻群演算法之特性，求解推銷員旅行問題。

Traveling Salesman Problem (TSP) is an optimization problems which emulates the salesperson to deliver goods. The problem is given a collection of cities and the cost of travel between each pair of cities. Find the cheapest way of to visit all the cities and return to the starting point. It is known as a NP-Complete problem. To solve these optimization problems we usually use Greedy Method which follows the problem solving heuristic of making the locally optimal choice at each stage and then use Neighborhood Exchange or Local Search method to improved. However, this way often converges to a local optimal solution. Thus, we use heuristic algorithms which emulates the characteristic of biological evolution behavior to find the global optimal solution.
This thesis we proposed Genetic Algorithm and Ant Colony Optimization that belong to heuristic algorithms. Using Genetic Algorithm to be the primary structure and get initial solution through three crossover approach then using the characteristic of Ant Colony Optimization to get the final solution of Traveling Salesman Problem.

[1] Flood, M.M.,“The traveling salesman problem”.Operation Research, Vol. 4 , pp.61-75,1956.
[2] Karp ,R.,(1972), “Reducibility among Combinatorial Problem ,”Complexity of Computer Computations ,Plenum Press, p p.85-104
[3] Lenstra ,J. K. and Rinnioy ,K. G..,“Some Simple Applications of the Traveling Salesman Problem”.Operational Research Quarterly,Vol.26, No.4,Part 1 Nov., pp. 717-733,1975.
[4] Garfinkel,R.S.Minimizing wallpaper waste,partI :“a class of traveling salesman problem”. Operation Research,Vol. 25, 99.741-751,1977.
[5] 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,Vol.26,pp.29-41.
[6] Holland,J.H.,(1975),“Adaptation in Natural and Artificial Systems,”Ann Arbor,MI：Univ,Michigan Press
[7]Lawler,E.l.,Lenstra,J.K.,Rinnooy Kan,A.H.G. and Shmoys,D.B.,(1985)“The Traveling Salesman Problem： A Guided Tour of Combinatorial Optimization.”Wiley and Sons.New York.
[8] Sharad,N. Kumbharana, Prof.Gopal M. Pandey (2013)，“A Comparative Study of ACO, GA and SA for Solving Travelling Salesman Problem”
[9] 鄧宇佑，「求解醫院運輸部門運輸中心個數最佳化之研究」，國立成功大學工業管理研究所論文，民國九十一年。
[10] 吳宗樺，「強化螞蟻驗演算法與禁忌搜尋法之混合模式於配水管網設計最佳化之應用」，國立中興大學環境工程學系碩士論文，民國九十三年。
[11] 劉昱德、黃士韜，「比較三種萬用啟發式演算法於TSP問題之探討」，工程技術與教育學刊第八卷第三期，民國一OO年9月。
[12]邱以強，「螞蟻演算法求解旅行推銷員問題」，國立東華大學資訊工程學碩士班，民國一O一年。