ANALYSIS AND SYNTHESIS OF ENHANCED BEE COLONY OPTIMIZATION WITH THE TRADITIONAL BEE COLONY OPTIMIZATION TO SOLVE TRAVELLING SALES PERSON PROBLEM
DOI:
https://doi.org/10.24297/ijct.v2i2b.6734Keywords:
Travelling Salesperson problem, Combinatorial Optimization, Bee Colony Algorithm, K-Means ClusteringAbstract
Bee colony optimization is the recent swarm intelligence technique which has been applied to solve many combinatorial problems. In this paper we propose the enhanced bee algorithm based on Kmeans clustering to solve TSP. In the proposed algorithm parallel bee algorithm has been applied to each cluster and connection method has been suggested to combine the sub tour to global tour of the whole cities. It was found the enhanced bee algorithm give the better result and more optimal tour.
Downloads
Download data is not yet available.
References
[1] E. Bonabeau, M. Dorigo, G. Theraulaz, “Swarm Intelligence: From Natural to Artificial Systemsâ€, New York, NY: Oxford University Press, 1999
[2] D.T. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim, M. Zaidi. "The Bees Algorithm - A Novel Tool for Complex Optimisation Problems" Proceedings of 2nd Virtual International Conference on Intelligent Production Machines and Systems (IPROMS 2006), The Internet, July 2006.
[3] D.L.Applegate, R.E.Bixby,V.Chvatal, and W. J. Cook, “The Traveling Salesman Problem: A Computational Studyâ€, Princeton University Press, 2006
[4] D.J Rosenkrantz,R.E Stearns and P.M Lewis†An Analysis of several heuristics for the travelling sales man problem†SIAM journal on computing ,vol 6 ,no. 3,pp.563-581,1977
[5] A.M Frieze,â€An extension of theChristofides Heuristics to the k-person travelling sales person problem,†discrete applied mathematics,vol 6,n0 1,pp 79-83,1983
[6] 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-Part A, vol.32, pp.72-77, 2002.
[7] Y. He, Y. Qiu, G. Liu and K. Lei, “A parallel adaptive tabu search approach for traveling salesman problems,†in Proceedings of IEEE International Conference on Natural Language Processing and Knowledge Engineering, 2005, pp.796-801.
[8] J.D. Wei and D.T. Lee, “A new approach to the traveling salesman problem using genetic algorithms with priority encoding,†in Proceedings of Congress on Evolutionary Computation, 2004, pp.1457- 1464.
[9] Marco Dorigo “Ant Colonies for the Traveling Salesman Problemâ€IRIDIA,Université Libre de Bruxelles. IEEE Transactions on Evolutionary Computation, 1(1):5366. 1997
[10] W.L. Zhong, J. Zhang and W.N. Chen,“A novel discrete particle swarmoptimization to solve traveling salesman problem,â€in Proceedings of IEEE Congress on Evolutionary Computation, 2007, pp.3283-3287.
[11] L. P. Wong, M. Y. H. Low, and C. S. Chong, “A bee colony optimization algorithm for traveling salesman problem,†in Proceedings of Second Asia International Conference on Modelling & Simulation (AMS 2008), 2008, pp. 818-823.
[12] C. S. Chong, Y. H. Malcolm Low, A. I. Sivakumar, and K. L. Gay, "A bee colony optimization algorithm to job shop scheduling," in Proceedings of the 2006 Winter Simulation Conference, 2006. pp. 1954-1961.
[13] D.T.Pham, A.Ghanbarzadeh, E.Koc, S.Otri, S.Rahim, M.Zaidi, “The Bees Algorithm – A Novel Tool for Complex Optimization Problemsâ€, International Virtual Conference on Intelligent Production Machine and Systems, 2006
[14] K. von Frisch, "Decoding the language of the bee," Science, vol. 185, no. 4152, pp. 663- 668, 1974.
[15] L. P. Wong, M. Y. H. Low, and C. S. Chongâ€Bee colony optimization with local search for the Travelling sales person problemâ€
[16] Dusan Teodorovic, Panta Lucic, Goran Markovic, Mauro Dell' Orco “Bee Colony Electrical Optimization: Principles and Applicationsâ€8th Seminar on Neural Network Applications in Engineering, NEUREL-2006
[17] Li-Pei Wong,Malcolm Yoke Hean Low,Chin Soon Chong(2009)â€An Efficient Bee Colony Optimization Algorithm for Traveling Salesman Problem using Frequency- based Pruningâ€
[2] D.T. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim, M. Zaidi. "The Bees Algorithm - A Novel Tool for Complex Optimisation Problems" Proceedings of 2nd Virtual International Conference on Intelligent Production Machines and Systems (IPROMS 2006), The Internet, July 2006.
[3] D.L.Applegate, R.E.Bixby,V.Chvatal, and W. J. Cook, “The Traveling Salesman Problem: A Computational Studyâ€, Princeton University Press, 2006
[4] D.J Rosenkrantz,R.E Stearns and P.M Lewis†An Analysis of several heuristics for the travelling sales man problem†SIAM journal on computing ,vol 6 ,no. 3,pp.563-581,1977
[5] A.M Frieze,â€An extension of theChristofides Heuristics to the k-person travelling sales person problem,†discrete applied mathematics,vol 6,n0 1,pp 79-83,1983
[6] 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-Part A, vol.32, pp.72-77, 2002.
[7] Y. He, Y. Qiu, G. Liu and K. Lei, “A parallel adaptive tabu search approach for traveling salesman problems,†in Proceedings of IEEE International Conference on Natural Language Processing and Knowledge Engineering, 2005, pp.796-801.
[8] J.D. Wei and D.T. Lee, “A new approach to the traveling salesman problem using genetic algorithms with priority encoding,†in Proceedings of Congress on Evolutionary Computation, 2004, pp.1457- 1464.
[9] Marco Dorigo “Ant Colonies for the Traveling Salesman Problemâ€IRIDIA,Université Libre de Bruxelles. IEEE Transactions on Evolutionary Computation, 1(1):5366. 1997
[10] W.L. Zhong, J. Zhang and W.N. Chen,“A novel discrete particle swarmoptimization to solve traveling salesman problem,â€in Proceedings of IEEE Congress on Evolutionary Computation, 2007, pp.3283-3287.
[11] L. P. Wong, M. Y. H. Low, and C. S. Chong, “A bee colony optimization algorithm for traveling salesman problem,†in Proceedings of Second Asia International Conference on Modelling & Simulation (AMS 2008), 2008, pp. 818-823.
[12] C. S. Chong, Y. H. Malcolm Low, A. I. Sivakumar, and K. L. Gay, "A bee colony optimization algorithm to job shop scheduling," in Proceedings of the 2006 Winter Simulation Conference, 2006. pp. 1954-1961.
[13] D.T.Pham, A.Ghanbarzadeh, E.Koc, S.Otri, S.Rahim, M.Zaidi, “The Bees Algorithm – A Novel Tool for Complex Optimization Problemsâ€, International Virtual Conference on Intelligent Production Machine and Systems, 2006
[14] K. von Frisch, "Decoding the language of the bee," Science, vol. 185, no. 4152, pp. 663- 668, 1974.
[15] L. P. Wong, M. Y. H. Low, and C. S. Chongâ€Bee colony optimization with local search for the Travelling sales person problemâ€
[16] Dusan Teodorovic, Panta Lucic, Goran Markovic, Mauro Dell' Orco “Bee Colony Electrical Optimization: Principles and Applicationsâ€8th Seminar on Neural Network Applications in Engineering, NEUREL-2006
[17] Li-Pei Wong,Malcolm Yoke Hean Low,Chin Soon Chong(2009)â€An Efficient Bee Colony Optimization Algorithm for Traveling Salesman Problem using Frequency- based Pruningâ€
Downloads
Published
2012-04-30
How to Cite
Agrawal, P., Kaur, H., & Bhardwaj, D. (2012). ANALYSIS AND SYNTHESIS OF ENHANCED BEE COLONY OPTIMIZATION WITH THE TRADITIONAL BEE COLONY OPTIMIZATION TO SOLVE TRAVELLING SALES PERSON PROBLEM. INTERNATIONAL JOURNAL OF COMPUTERS &Amp; TECHNOLOGY, 2(2), 93–97. https://doi.org/10.24297/ijct.v2i2b.6734
Issue
Section
Research Articles
