Artificial Bee Colony Algorithm for Traveling Salesman Problem

Article Preview

Abstract:

By combining the modified nearest neighbor approach and the improved inver-over operation, an Artificial Bee Colony (ABC) Algorithm for Traveling Salesman Problem (TSP) is proposed in this paper. The heuristic approach was tested in some benchmark instances selected from TSPLIB. In addition, a comparison study between the proposed algorithm and the Bee Colony Optimization (BCO) model is presented. Experimental results show that the presented algorithm outperforms the BCO method and can efficiently tackle the small and medium scale TSP instances.

You might also be interested in these eBooks

Info:

Periodical:

Advanced Materials Research (Volumes 314-316)

Pages:

2191-2196

Citation:

Online since:

August 2011

Export:

Price:

Permissions CCC:

Permissions PLS:

Сopyright:

© 2011 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

[1] Michael, J., Gerhard,Rand. and Giovanni,R., The Traveling Salesman Problem, Handbooks in Operations Research and Management Science, 7, 1995, 225 - 330.

Google Scholar

[2] Munakata, T., Y, Nakamura. Temperature control for simulated annealing, Physical Review 64, 2001, 46 - 127.

Google Scholar

[3] Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I. and Dizdarevic,S., Genetic Algorithms for the Traveling Salesman Problem: A Review of Representations and Operators, Artificial Intelligence Review. 13, 1999, 129 - 170.

DOI: 10.1023/a:1006529012972

Google Scholar

[4] Dorigo,M., Gambardella, L.M., Ant colony system: a cooperative learning approach to the traveling salesman problem,  Evolutionary Computation, IEEE Transactions, 1 ,1997, 53 - 66.

DOI: 10.1109/4235.585892

Google Scholar

[5] W.L. Zhong, J. Zhang and W.N. Chen, A Novel Discrete Particle Swarm Optimization to solve Traveling Salesman Problem, IEEE Congress on Evolutionary Computation, 2007, 3283 - 3287.

DOI: 10.1109/cec.2007.4424894

Google Scholar

[6] Karaboga, D., An idea based on honey bee swarm for numerical optimization, Technical Report TR06, Computer Engineering Department, Erciyes University,Turkey, 2005.

Google Scholar

[7] Karaboga, D., Basturk, B., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of Global Optimization, 39, 2007, 459–471.

DOI: 10.1007/s10898-007-9149-x

Google Scholar

[8] Karaboga, D., Basturk, B., On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8, 2008, 687 - 697.

DOI: 10.1016/j.asoc.2007.05.007

Google Scholar

[9] Karaboga, D., Basturk, B., Artificial Bee Colony (ABC) algorithm for Solving Constrained Optimization Problem, Foundations of Fuzzy Logic and Soft Computing, 4529, 2007, 789 – 798.

DOI: 10.1007/978-3-540-72950-1_77

Google Scholar

[10] Pulikanti, S., Singh, A., An Artificial Bee Colony Algorithm for the Quadratic Knapsack Problem, Neural information processing, 5864, 2009, 196 – 295.

DOI: 10.1007/978-3-642-10684-2_22

Google Scholar

[11] Singh, A., An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem, Applied Soft Computing, 9, 2009, 625 – 631.

DOI: 10.1016/j.asoc.2008.09.001

Google Scholar

[12] Baykasoglu, A., Ozbakir, L., Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem, Focus on Ant and Particle Swarm Optimization, 2007, 114 – 144.

DOI: 10.5772/5101

Google Scholar

[13] Sundar, S., Singh, A., A swarm intelligence approach to the quadratic minimum spanning, Information Science, 17,2010, 3182 – 3191.

DOI: 10.1016/j.ins.2010.05.001

Google Scholar

[14] Rosenkrantz, D.J., Stearns, R.E. and Lewis, P.M., An analysis of several heuristics for the traveling salesman problem, Fundamental Problem in Computing, 1, 2009, 45 – 69.

DOI: 10.1007/978-1-4020-9688-4_3

Google Scholar

[15] Tao, G., Michalewicz, Z., Inver-over operator for the TSP, Parallel Problem Solving from Nature, 1498, 1998, 803 – 812.

DOI: 10.1007/bfb0056922

Google Scholar

[16] Lin, S., Kerninghan, B.W., An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research, 1972, 498 – 516.

DOI: 10.1287/opre.21.2.498

Google Scholar

[17] G. Reinelt, TSPLIB—A traveling salesman problem library, ORSA Journal on Computing, 3, 1991, 376–384.

DOI: 10.1287/ijoc.3.4.376

Google Scholar

[18] Wong L. P., Low, M.Y.H. and Chong, C.S., A bee colony optimization algorithm for traveling salesman problem, in Proceedings of Second Asia International Conference on Modeling and Simulation, 2008, 818-823.

DOI: 10.1109/ams.2008.27

Google Scholar