The Cluster Crossover Operation for The Symmetric Travelling Salesman Problem

Article Sidebar

PDF
Published: Feb 18, 2019
DOI: https://doi.org/10.37936/ecti-cit.2018122.132018
Keywords:
Travelling Salesman Cluster Crossover Clockwise Search Galaxy Based Search

Main Article Content

Ajchara Phu-ang
Department of Information Technology, Chandrakasem Rajabhat University, Thailand
Duangjai Jitkongchuen
College of Innovative Technology and Engineering, Dhurakij Pundit University, Thailand

Abstract

This paper proposed the new algorithm intended to solve a specific real-world problem, the symmetric travelling salesman problem. The proposed algorithm is based on the concept of the galaxy based search algorithm (GbSA) and  embedded the new ideas called the clockwise search process and the cluster crossover operation. In the first step, the nearest neighbor algorithm introduces to generate the initial population. Then, the tabu list local search is employed to search for the new solution in surrounding areas of the initial population in the second step. The clockwise search process and the cluster crossover operation are employed to create more diversity of the new solution. Then, the final step, the hill climbing local search is utilized to increase the local search capabilities. The experiments with the standard benchmark test sets show that the proposed algorithm can be found the best average percentage deviation from the lower bound.

Article Details

How to Cite
[1]
A. Phu-ang and D. Jitkongchuen, “The Cluster Crossover Operation for The Symmetric Travelling Salesman Problem”, ECTI-CIT Transactions, vol. 12, no. 2, pp. 98–105, Feb. 2019.
Issue
Vol. 12 No. 2 (2018): ECTI Transaction on CIT (Nov 2018)
Section
Artificial Intelligence and Machine Learning (AI)

References

[1] M. Mahi, O. K. Baykan and H. Kodaz, “A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem,” Applied Soft Computing, vol. 30, pp. 484-490, 2015.

[2] E. Osaba, X. S. Yang, F. Diaz, P. Lopez-Garcia and R. Carballedo, “An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems,” Engineering Applications of Artificial Intelligence, vol 48, pp. 59-71, 2016.

[3] G. E. A. Fuentes, E. S. H. Gress, J. C. S. T. Mora and J. M. Mar ́ın, “Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic,” PLoS ONE, vol. 13(8), pp.1-20, 2018.

[4] S. Meneses, R. Cueva, M. Tupia and M. Guanira, “A Genetic Algorithm to Solve 3D Traveling Salesman Problem with Initial Population Based on a GRASP Algorithm,” Journal of Computational Methods in Sciences and Engineering, vol. 17, pp. 1-10, 2017.

[5] J. Sung and B. Jeong, “An Adaptive Evolutionary Algorithm for Traveling Salesman Problem with Precedence Constraints,” The Scienti c World Journal, vol.2014, pp.1-14.

[6] Y. Wang, “The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem,”
Computers & Industrial Engineering, vol. 70, pp. 124-133, 2014.

[7] A. Srour, Z. A. Othman and A. R. Hamdan, “A Water Flow-Like Algorithm for the Travelling Salesman Problem,”
Advances in Computer En- gineering, vol. 2014, pp. 1-14.

[8] T. A.S. Masutti and L. N. de Castro, “A self organizing neural network using ideas from the immune system to solve the traveling salesman problem,” Information Sciences, vol. 179, pp. 1454-1468, 2009.

[9] R. Matai, S. Singh and M. Lal Mittal, Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches, Traveling Salesman Problem, Theory and Applications, Prof. Donald Davendra (Ed.), ISBN: 978-953-307-426-9, InTech., 2010.

[10] H. Shah-Hosseini, “Principal components analysis by the galaxy based search algorithm: A novel metaheuristic for continuous optimization,” Int. J. Computational Science and Engineering, vol. 6, pp. 132-140, 2011.

[11] Fred Glover, “Tabu Search - Part 2,” ORSA Journal on Computing, vol. 2, no.1, pp. 4-32, 1990.

[12] D.B. Fogel, “An evolutionary approach to the travelling salesman problem,” Biological Cybernetics, vol. 60, pp.139-144, 1988.