旅行銷售員問題是一個著名的NP-hard問題，這類的問題非常難以找到最佳解。螞蟻族群最佳化則是近年來所提出的巨集式啟發演算法，且已經成功的應用於解決組合最佳化問題。螞蟻族群演算法是藉由生物上對真實螞蟻搜尋食物的行為中所得到的啟發。當螞蟻搜索食物時，是根據之前螞蟻往返路徑時所留下的費洛蒙濃度來決定所走的路徑。雖然螞蟻族群演算法在最佳化問題上已經有很好的尋優能力，它仍有些缺點如:停滯行為、長時間的計算及過早收斂等問題。當旅行城市數目增加時，這些問題將更為明顯。
在本篇論文中，提出兩個啟發式的方法去改善螞蟻族群最佳化演算法(Ant Colony Optimization, ACO)應用於解決旅行銷售員問題(Traveling Salesman Problem, TSP)的解題效率。首先提出的第一個方法是將精英政策應用於螞蟻建構路徑時的機率候選。我們將欲旅行的城市做一合理選擇，如此可以縮減龐大的解空間，使系統的效能得以提升。第二個方法，則是利用圖形上的觀察所得到的啟發。此啟發是以偵測路徑交叉並修正交叉的方式，將路徑總值降低。
實驗結果顯示，我們將精英候選範圍設定在資料集合城市數的十個百分比至十五個百分比時，在相同運算時間之下，表現的比螞蟻族群最佳化有更好的結果。而修正交叉路徑的方法適用於所有的資料集合，且執行時間相當短。

The Traveling Salesman Problems(TSP) are well known as NP-hard problems which are difficult and time-consuming. Ant Colony Optimization(ACO) is a new proposed metaheuristic algorithm that has been successfully applied to solving Combinatorial Optimization Problems(COP). ACO is biologically inspired by observing the behavior of real ants, and it simulates the process of ants searching for food. When ants forage the food, they depend on the amount of pheromone deposited on the traverse path. Although ACO algorithm has very good searching capability in optimization problems, it still has some drawbacks such as stagnation behavior, needing longer computing time, and premature convergence. These drawbacks will be more evident when the problem size increases.
In this thesis, we propose two heuristic methods to improve the efficiency of ACO in solving the Traveling Salesman Problem. First, we apply the elitism to the probability candidates for the ants to construct the tours. Second, we are inspired by observing the route maps to develop a heuristic method which makes the edges not cross and shortens the route.
In our experimental results, the first method of choosing the elitism list from ten to fifteen percentage of the city size for the ants to forward the next city achieves better performance than ACO under the condition of spending the same time. The second method of the solving crossing routes can be applied well to all scale of data set and only cost a short time to improve.

[1].http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[2].T. Stutzle, and H. H. Hoos, “Max-Min Ant System”, Journal of Future Generation Computer Systems, vol 16, pp. 889-914, 2000.
[3].B. Bullnheimer, R.F. Hartl, and C. Strauss, “A new rank based version of the ant system---A computational study”, Central European Journal of Operations Research, vol. 7, pp. 25-38, 1999.
[4].L. M. Gambardella, and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem”, International Conference on Machine Learning, pp. 252-260, 1995.
[5].R. Kumar, and Z. Luo, “Optimizing the operation sequence of a chip placement machine using tsp model”, IEEE Transactions on Electronics Packaging Manufacturing, vol. 26, no. 1, 2003.
[6].D. Chan, and D. Mercier, “IC insertion: an application of the traveling salesman problem”, International Journal of Production Research, pp. 1837-1841, 1989.
[7].K. Fujimura, K. Obu-Cann, and H. Tokutaka, “Optimization of surface component mounting on the printed circuit board using SOM-TSP method”, International Conference on Digital Object Identifier, vol 1. pp. 16-20, 1999.
[8].H. Jula, M. Dessouky, and P. A. Ioannou, “Truck route planning in nonstationary stochastic networks with time windows at customer locations”, IEEE Transactions on Intelligent Transportation Systems, vol. 7, no. 1, 2006..
[9].K. Savla, F. Bullo, and E. Frazzoli, “On traveling salesperson Problem for Dubins’ vehicle: stochastic and dynamic environments”, IEEE Conference on Decision and Control, pp. 4530-4535, 2005.
[10].D. F. Wong, and M. Shao, “The bi-weighted TSP problem for VLSI crosstalk minimization”, IEEE Conference on Digital Object Identifier, vol. 3, pp. 767-770, 2002.
[11].J. W. Pepper, B. L. Golden, and E. A. Wasil, “Solving the Traveling salesman problem with annealing-based heuristics: A computational study”, IEEE Transactions on Systems, Man, and Cybernetics, vol. 32, no. 1, 2002.
[12].J. Gu., and X. Huang, “Efficient local search with search space smoothing: A case study of the traveling salesman problem(TSP)”, IEEE Transactions on Systems, Man, and Cybernetics, vol. 24, no. 5, 1994.
[13].R. Baraglia, J. I. Hidalgo, and R. Perego, “A hybrid heuristic for the traveling problem”, IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, 2001.
[14].E. Aarts, and J. K. Lenstra, Local search in combinatorial optimization, John Wiley & Sons Inc., 1997.
[15].S. Lin, and B. W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,” Operations Research, vol. 21, no. 2, pp. 498-516, 1973.
[16].M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics, Part B, vol. 26, pp. 29-41, 1996.
[17].M. Dorigo and G. D. Caro, “Ant colony optimization: A new meta-heuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, vol.2, pp. 1470-1477, 1999.
[18].T. Stutzle, and M. Dorigo, Ant colony optimization, MIT Press, 2004
[19].M. Dorigo, and L. M. Gambardella, “The colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, April, 1997.
[20].A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proc. of ECAL91-European Conference on Artificial Life, pp. 134-142, 1991.
[21].D. J. Rosenkranz, R. E. Stearns, and P. M. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal on Computing, vol. 6, pp. 563-581, 1997.
[22].E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence from natural to artificial systems, Oxford University Press, 1999.