Download fulltext HTML
Saud, S., Kodaz, H., & Babaoğlu, İsmail. (2018). Solving Travelling Salesman Problem by Using Optimization Algorithms. KnE Social Sciences, 3(1), 17-32. https://doi.org/10.18502/kss.v3i1.1394

https://doi.org/10.18502/kss.v3i1.1394

statistics

  • 8669 Abstract Views
  • 1800 PDF Views
  • 0 HTML Views

authors

  • Suhair Saud

    Suhair Saud

    Dept. of Computer Engineering, Faculty of Engineering, Selcuk University, Konya
  • Halife Kodaz

    Halife Kodaz

    Dept. of Computer Engineering, Faculty of Engineering, Selcuk University, Konya
  • İsmail Babaoğlu

    İsmail Babaoğlu

    Dept. of Computer Engineering, Faculty of Engineering, Selcuk University, Konya

Published Date

  • Jan 15, 2018

Solving Travelling Salesman Problem by Using Optimization Algorithms

KnE Social Sciences / The 9th International Conference on Advances in Information Technology (IAIT-2017) / Pages 17-32

Abstract

This paper presents the performances of different types of optimization techniques used in artificial intelligence (AI), these are Ant Colony Optimization (ACO), Improved Particle Swarm Optimization with a new operator (IPSO), Shuffled Frog Leaping Algorithms (SFLA) and modified shuffled frog leaping algorithm by using a crossover and mutation operators. They were used to solve the traveling salesman problem (TSP) which is one of the popular and classical route planning problems of research and it is considered  as one of the widely known of combinatorial optimization. Combinatorial optimization problems are usually simple to state but very difficult to solve. ACO, PSO, and SFLA are intelligent meta-heuristic optimization algorithms with strong ability to analyze the optimization problems and find the optimal solution. They were tested on benchmark problems from TSPLIB and the test results were compared with each other.

Keywords: Ant colony optimization, shuffled frog leaping algorithms, travelling salesman problem, improved particle swarm optimization

References
[1] F. Greco, ”Travelling Salesman Problem, I-Tech,” ed: Croatia, 2008.


[2] H. Dikmen, H. Dikmen, A. Elbir, Z. Ekşi, and F. Çelik, ”Gezgin Satici Probleminin Karinca Kolonisi ve Genetik Algoritmalarla Eniyilemesi ve Karsilastirilmasi,” Journal of Natural & Applied Sciences, vol. 18, 2014.


[3] X. Yan, C. Zhang, W. Luo, W. Li, W. Chen, and H. Liu, ”Solve traveling salesman problem using particle swarm optimization algorithm,” International Journal of Computer Science, vol. 9, pp. 264-271, 2012.


[4] M. Dorigo, V. Maniezzo, and A. Colorni, ”The ant system: Optimization by a colony of cooperative agents,” 1996.


[5] Z. C. S. S. Hlaing and M. A. Khine, ”Solving traveling salesman problem by using improved ant colony optimization algorithm,” International Journal of Information and Education Technology, vol. 1, p. 404, 2011.


[6] M. Eusuff, K. Lansey, and F. Pasha, ”Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization,” Engineering optimization, vol. 38, pp. 129- 154, 2006.


[7] X.-h. Luo, Y. Yang, and X. Li, ”Solving TSP with shuffled frog-leaping algorithm,” in Intelligent Systems Design and Applications, 2008. ISDA’08. Eighth International Conference on, 2008, pp. 228-232.


[8] M. Wang and W. Di, ”A modified shuffled frog leaping algorithm for the traveling salesman problem,” in Natural Computation (ICNC), 2010 Sixth International Conference on, 2010, pp. 3701-3705.


[9] P. Larranaga, C. M. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, ”Genetic algorithms for the travelling salesman problem: A review of representations and operators,” Artificial Intelligence Review, vol. 13, pp. 129-170, 1999.


[10] I. Oliver, D. Smith, and J. R. Holland, ”Study of permutation crossover operators on the traveling salesman problem,” in Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28- 31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA, 1987.


[11] A. Umbarkar and P. Sheth, ”Crossover Operators In Genetic Algorithms: A Review,” ICTACT journal on soft computing, vol. 6, 2015.


[12] D. B. Fogel and J. W. Atmar, ”Comparing genetic operators with Gaussian mutations in simulated evolutionary processes using linear systems,” Biological Cybernetics, vol. 63, pp. 111-114, 1990.


[13] H. H. Chieng, ”A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem,” Universiti Tun Hussein Onn Malaysia, 2016.


[14] L. Davis, ”Job shop scheduling with genetic algorithms,” in Proceedings of an international conference on genetic algorithms and their applications, 1985.


[15] N. Kumar and R. K. Karambir, ”A comparative analysis of pmx, cx and ox crossover operators for solving traveling salesman problem,” International journal of Latest Research in science and technology, vol. 1, 2012.


[16] F. Huilian, ”Discrete particle swarm optimization for TSP based on neighborhood,” Journal of Computational Information Systems, vol. 6, pp. 3407-3414, 2010.


[17] R. Eberhart and J. Kennedy, ”A new optimizer using particle swarm theory,” in Micro Machine and Human Science, 1995. MHS’95., Proceedings of the Sixth International Symposium on, 1995, pp. 39-43.


[18] F. Heppner and U. Grenander, ”A stochastic nonlinear model for coordinated bird flocks,” The ubiquity of chaos, pp. 233-238, 1990.


[19] I. Yaman, ”Portfy optimizasyonunda değiştirilmiş parçac