Application of Ant Colony Optimization for the Solution of 3 Dimensional Cuboid Structures

Hüseyin Eldem, Erkan Ülker

Computer Engineering Department, Sel?uk University, Konya, Turkey.
Computer Technologies Department, Karamano?lu Mehmetbey University, Karaman, Turkey.

DOI: 10.4236/jcc.2014.24014                

Abstract

Traveling Salesman Problem (TSP) is one of the most widely studied real world problems of finding the shortest (minimum cost) possible route that visits each node in a given set of nodes (cities) once and then returns to origin city. The optimization of cuboid areas has potential samples that can be adapted to real world. Cuboid surfaces of buildings, rooms, furniture etc. can be given as examples. Many optimization algorithms have been used in solution of optimization problems at present. Among them, meta-heuristic algorithms come first. In this study, ant colony optimization, one of meta-heuristic methods, is applied to solve Euclidian TSP consisting of nine different sized sets of nodes randomly placed on a cuboid surface. The performance of this method is shown in tests.

Keywords

Euclidean TSP; Ant Colony Optimization; Metaheuristic; Path-Relinking; Path Planning; Cuboid

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Arora, S. (1996) Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, 14-16 October 1996, 2-11.
[2]	Kirkpatrick, S., Gelatt, C.D. and Vecchi M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671-680. http://dx.doi.org/10.1126/science.220.4598.671
[3]	Tsujimura, Y. and Gen, M. (1998) Entropy-Based Genetic Algorithm for Solving TSP. Knowledge-Based Intelligent Electronic Systems, Adelaide, 285-290.
[4]	Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading.
[5]	Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
[6]	Glover, F. (1989) Tabu Search—Part I. ORSA Journal on Computing, 1, 190-206. http://dx.doi.org/10.1287/ijoc.1.3.190
[7]	Glover, F. (1990) Tabu Search—Part II. ORSA Journal on Computing, 2, 4-32. http://dx.doi.org/10.1287/ijoc.1.3.190
[8]	Hopfield, J.J. and Tank, D.W. (1985) Neural Computation of Decisions in Optimization Problems. Biological Cybernetics, 52, 141-152.
[9]	Kohonen, T. (1995) Self-Organizing Maps. Springer, Berlin. http://dx.doi.org/10.1007/978-3-642-97610-0
[10]	Shinozawa, K., Uchiyama, T. and Shimohara, K. (1991) An Approach for Solving Dynamic TSPs Using Neural Networks. Proceedings of the IEEE International Joint Conference on Neural Networks, 3, 2450-2454.
[11]	Colorni, A., Dorigo, M. and Maniezzo, V. (1991) Distributed Optimization by Ant Colonies. In: Varela, F. and Bourgine, P., Eds., Proceedings of the European Conference on Artificial Life, ECAL’91, Paris, Elsevier Publishing, Amsterdam, 134-142.
[12]	Colorni, A., Dorigo, M. and Maniezzo, V. (1992) An Investigation of Some Properties of an Ant Algorithm. In: Maenner, R. and Manderick, B., Eds., Proceedings of the Second Conference on Parallel Problem Solving from Na- ture, Brussels, PPSN II, North-Holland, Amsterdam, 509- 520.
[13]	Dorigo, M. (1992) Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, Italy.
[14]	Gambardella, L.M. and Dorigo, M. (1996) Solving Symmetric and Asymmetric TSPs by Ant Colonies. Proceedings of the International Conference on Evolutionary Computation, Nagoya, 20-22 May 1996, 622-627.
[15]	Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 53-66.
[16]	Dorigo, M. and Gambardella L.M. (1997) Ant Colonies for the Travelling Salesman Problem. Biosystems, 43, 73-81. http://dx.doi.org/10.1016/S0303-2647(97)01708-5
[17]	Johnson, D.S. and McGeoch, L.A. (1997) The Traveling Salesman Problem: A Case Study in Local Optimization. In: Aarts, E.H.L. and Lenstra, J.K., Eds., Local Search in Combinatorial Optimization, John Wiley & Sons, New York, 215-310.
[18]	Lee, Z.J. (2004) A Hybrid Algorithm Applied to Travelling Salesman Problem. Networking, Sensing and Control, Proceedings of the IEEE International Conference, 237-242.
[19]	White, C.M. and Yen, G.G. (2004) A Hybrid Evolutionary Algorithm for Traveling Salesman Problem. Congress on Evolutionary Computation (CEC2004), 1473-1478.
[20]	Marinakis, Y., Migdalas, A. and Pardalos, P.M. (2005) A Hybrid Genetic-GRASP Algorithm Using Lagrangean Relaxation for the Traveling Salesman Problem. Journal of Combinatorial Optimization, 10, 311-326. http://dx.doi.org/10.1007/s10878-005-4921-7
[21]	Tsai, C., Tsai, C. and Tseng, C. (2004) A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem. Information Sciences, 166, 67-81. http://dx.doi.org/10.1016/j.ins.2003.11.008
[22]	U?ur, A. (2008) Path Planning on a Cuboid Using Genetic Algorithms. Information Sciences, 178, 3275-3287. http://dx.doi.org/10.1016/j.ins.2008.04.005
[23]	Su, S.B. and Cao, X.B. (2013) Jumping PSO with Expanding Neigh-borhood Search for TSP on a Cuboid. Chinese Journal of Electronics, 22, 202-208.
[24]	Uğur, A., Korukoğlu, S., Cal?skan, A., Cinsdikici, M. and Alp, A. (2009) Genetic Algorithm Based Solution for Tsp on a Sphere. Mathematical and Computational Applications, 14, 219-228.