A Proposed Approach For Solving Asymmetric Travelling Salesman Problem by Fuzzy Ant Colony Optimization Algorithm

Year 2018, Volume: 3 Issue: 1, 25 - 34, 15.04.2018

Osman Pala , Mehmet Aksaraylı

Abstract

Logistics sector is one of the most prominent field in economic development of a country. Travelling Salesman Problem which is studied commonly in logistic sector is also based a number of other problems. Shortly, it is aimed to travel along to n locations with limitation of only visiting each location once. Due to NP-hard nature of problem, it is becoming impossible to find exact solution when the number of locations are above a certain level. Due to this reason, heuristic methods are mainly used for solving Travelling Salesman Problem. Ant Colony Optimization Algorithm which is a heuristic method that uses swarm intelligence gives good solutions in solving combinatorial optimization problems. In this study, Ant System and Ant Colony System are tested according to proposed principal of well distributed initial locations and different values of parameters for solving asymmetric Travelling Salesman Problem. Test problem which is in literature is solved by program that is coded in MATLAB programming language. Statistical analysis which is conducted on results indicate that proposed approach provides significant contribution on solutions.

Keywords

Travelling Salesman Problem, Ant Colony Optimization Algorithm, Swarm Intelligence

Asimetrik Gezgin Satıcı Problemine Bulanık Karınca Kolonisi Optimizasyon Algoritmasi İle Çözüm Yaklaşımı

Abstract

Lojistik sektörü bir ülkenin ekonomik gelişiminde en önemli yer tutan alanlardan birisidir. Gezgin Satıcı Problemi, lojistik sektöründe çokça çalışılan ve başka birçok probleme temel olan bir problemdir. Problem kısaca n adet noktaya birer kere uğramak koşulu ile en kısa yoldan n adet noktayı ziyareti amaçlar. Problemin NP-zor olması, uğranılması gereken nokta sayısı belirli bir seviyenin üzerinde kesin sonuç elde etmeyi zorlaştırmaktadır. Bu nedenle Gezgin Satıcı Probleminin çözümünde sezgisel yöntemler öne çıkmaktadır. Sürü zekasını kullanan sezgisel yöntemler arasında bulunan Karınca Kolonisi Optimizasyon Algoritması, kombinasyonel optimizasyon problemlerinin çözümünde oldukça iyi sonuçlar sunmaktadır. Çalışmada Karınca Sistemi ve Karınca Kolonisi Sistemi, önerilen iyi dağıtılmış başlangıç noktaları prensibine göre Asimetrik Gezgin Satıcı Probleminde farklı parametre değerleriyle test edilmiştir. MATLAB programlama dilinde yazılan program kullanılarak literatürde yer alan test problemleri çözülmüştür. Sonuçlar üzerinde yapılan istatistiksel analizler, önerilen değişikliğin çözüm değerlerine anlamlı katkı yaptığı yönündedir.

Keywords

Gezgin Satıcı Problemi, Karınca Kolonisi Optimizasyon Algoritması, Sürü Zekası

References

• Castillo, O., Neyoy, H., Soria, J., García, M., ve Valdez, F. (2013). Dynamic fuzzy logic parameter tuning for ACO and its application in the fuzzy logic control of an autonomous mobile robot. International Journal of Advanced Robotic Systems, 10(1), 51.
• Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy.
• Dorigo, M., ve Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.
• Dorigo, M., ve Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical computer science, 344(2-3), 243-278.
• Dorigo, M., Maniezzo, V., ve Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.
• Fiechter, C. N. (1994). A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, 51(3), 243-267.
• Förster, M., Bickel, B., Hardung, B., ve Kókai, G. (2007, July). Self-adaptive ant colony optimisation applied to function allocation in vehicle networks. In Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (pp. 1991-1998). ACM.
• Gambardella, L. M., ve Dorigo, M. (1996, May). Solving symmetric and asymmetric TSPs by ant colonies. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on (pp. 622-627). IEEE.
• Gendreau, M., Laporte, G., ve Semet, F. (1998). A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, 106(2-3), 539-545.
• Geng, X., Chen, Z., Yang, W., Shi, D., ve Zhao, K. (2011). Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Applied Soft Computing, 11(4), 3680-3689.
• Goldbarg, E. F. G., de Souza, G. R., ve Goldbarg, M. C. (2006, April). Particle swarm for the traveling salesman problem. In EvoCOP (Vol. 3906, pp. 99-110).
• Hlaing, Z. C. S. S., ve Khine, M. A. (2011). Solving traveling salesman problem by using improved ant colony optimization algorithm. International Journal of Information and Education Technology, 1(5), 404.
• Jun-man, K., ve Yi, Z. (2012). Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia, 17, 319-325.
• Kirkpatrick, S., Gelatt, C. D., ve Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
• Li, Y., ve Li, W. (2007). Adaptive ant colony optimization algorithm based on information entropy: Foundation and application. Fundamenta Informaticae, 77(3), 229-242.
• Malek, M., Guruswamy, M., Pandya, M., ve Owens, H. (1989). Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Annals of Operations Research, 21(1), 59-84.
• Moon, C., Kim, J., Choi, G., ve Seo, Y. (2002). An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research, 140(3), 606-617.
• Neyoy, H., Castillo, O., ve Soria, J. (2013). Dynamic fuzzy logic parameter tuning for ACO and its application in TSP problems. In Recent Advances on Hybrid Intelligent Systems (pp. 259-271). Springer Berlin Heidelberg.
• Niknam, T. (2010). A new fuzzy adaptive hybrid particle swarm optimization algorithm for non-linear, non-smooth and non-convex economic dispatch problem. Applied Energy, 87(1), 327-339.
• Pang, W., Wang, K. P., Zhou, C. G., ve Dong, L. J. (2004, September). Fuzzy discrete particle swarm optimization for solving traveling salesman problem. In Computer and Information Technology, 2004. CIT'04. The Fourth International Conference on (pp. 796-800). IEEE.
• Potvin, J. Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63(3), 337-370.
• Raman, V., ve Gill, N. S. (2017). Review of different heuristic algorithms for solving Travelling Salesman Problem. International Journal, 8(5). 423-425.
• Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA journal on computing, 3(4), 376-384.
• Shi, Y., ve Eberhart, R. C. (2001). Fuzzy adaptive particle swarm optimization. In Evolutionary Computation, 2001. Proceedings of the 2001 Congress on (Vol. 1, pp. 101-106). IEEE.