Md. Azizur Rahman; Kazi Mohammad Nazib; Md. Rafsan Islam; Lasker Ershad Ali

Solving Traveling Salesman Problem Through Genetic Algorithm with Clustering

PDF (1028KB), PP.15-33

Views: 0 Downloads: 0

Author(s)

Md. Azizur Rahman ^1,* Kazi Mohammad Nazib ¹ Md. Rafsan Islam ² Lasker Ershad Ali ¹

1. Mathematics Discipline, Science, Engineering and Technology School, Khulna University, Khulna, 9208, Bangladesh

2. Department of Mathematics, Hamdard University Bangladesh, Gazaria, Munshiganj, 1510, Bangladesh

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2025.03.02

Received: 11 Nov. 2024 / Revised: 28 Jan. 2025 / Accepted: 5 Feb. 2025 / Published: 8 Jun. 2025

Index Terms

Traveling Salesperson Problem (TSP), Genetic Algorithm (GA), Fuzzy C-means, K-means, K-medoids, Local Search Mechanism

Abstract

The Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem, commonly studied in computer science and operations research. Due to its complexity and broad applicability, various algorithms have been designed and developed from the viewpoint of intelligent search. In this paper, we propose a two-stage method based on the clustering concept integrated with an intelligent search technique. In the first stage, a set of clustering techniques - fuzzy c-means (FCM), k-means (KM), and k-mediods (KMD) - are employed independently to generate feasible routes for the TSP. These routes are then optimized in the second stage using an improved Genetic Algorithm (IGA). Actually, we enhance the traditional Genetic Algorithm (GA) through an advanced selection strategy, a new position-based heuristic crossover, and a supervised mutation mechanism (FIB). This IGA is implemented to the feasible routes generated in the clustering stage to search the optimized route. The overall solution approach results in three distinct pathways: FCM+IGA, KM+IGA, and KMD+IGA. Simulation results with 47 benchmark TSP datasets demonstrate that the proposed FCM+IGA performs better than both KM+IGA and KMD+IGA. Moreover, FCM+IGA outperforms other clustering-based algorithms and several state-of-the-art methods in terms of solution quality.

Cite This Paper

Md. Azizur Rahman, Kazi Mohammad Nazib, Md. Rafsan Islam, Lasker Ershad Ali, "Solving Traveling Salesman Problem Through Genetic Algorithm with Clustering", International Journal of Intelligent Systems and Applications(IJISA), Vol.17, No.3, pp.15-33, 2025. DOI:10.5815/ijisa.2025.03.02

Reference

[1]N. Deo, “Paths and circuits,” in Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, nc, 1974, pp. 34–35.
[2]Q. T. Luu, “Traveling salesman problem: Exact solutions vs. heuristic vs. approximation algorithms,” Baeldung on Computer Science, 2023. [Online]. Available: https:/ /www.baeldung.com /cs/tsp- exact-solutions-vs-heuristic-vs-approximation-algorithms.
[3]J. Clausen, “Branch and bound algorithms-principles and examples,” Department of Computer Science, University of Copenhagen, pp. 1–30, 1999.
[4]M. S. Levine, “Finding the right cutting planes for the tsp,” Journal of Experimental Algorithmics (JEA), vol. 5, 6–es, 2000. https://doi.org/10.1145/351827.384248.
[5]D. Karapetyan and G. Gutin, “Lin–kernighan heuristic adaptations for the generalized traveling salesman problem,” European Journal of Operational Research, vol. 208, pp. 221–232, 2011. https://doi.org/10.1016/j.ejor.2010.08.011.
[6]A. B. Kahng and S. Reda, “Match twice and stitch: A new tsp tour construction heuristic,” Operations Research Letters, vol. 32, pp. 499–509, 2004. https://doi.org/10.1016/j.orl.2004.04.001.
[7]H. Mo and L. Xu, “Biogeography migration algorithm for traveling salesman problem,” International Journal of Intelligent Computing and Cybernetics, vol. 4, pp. 311–330, 2011. DOI10.1108/17563781111160002.
[8]X. S. Yang, Nature-Inspired Metaheuristic Algorithms. Luniver Press, 2010.
[9]H. F. Amaral, S. Urrutia, and L. M. Hvattum, “Delayed improvement local search,” Journal of Heuristics, vol. 27, pp. 923–950, 2021. https://doi.org/10.1007/s10732-021-09479-9.
[10]D. Gupta, “Solving tsp using various meta-heuristic algorithms,” International Journal of Recent Contributions from Engineering, Science IT (iJES), vol. 1, pp. 22–26, 2013. DOI: http://dx.doi.org/10.3991/ijes.v1i2.3233.
[11]V. J. Sudhakar and V. N. Kumar, “A new approach to solve the classical symmetric traveling salesman problem by zero suffix method,” Int. J. Contemp. Math. Sciences, vol. 6(23), pp. 1111–1120, 2011.
[12]A. Philip, A. A. Taofiki, and O. Kehinde, “A genetic algorithm for solving travelling salesman problem,” International Journal of Advanced Computer Science and Applications (IJACSA), vol. 2(1), pp. 26–29, 2011. [Online]. Available: https://ir.unilag.edu.ng/handle/123456789/5461.
[13]Y. Wang and Z. Han, “Ant colony optimization for traveling salesman problem based on parameters optimization,” Applied Soft Computing, vol. 107, p. 107 439, 2021. https://doi.org/10.1016/j.asoc.2021.107439.
[14]I. Khan and M. K. Maiti, “A swap sequence based artificial bee colony algorithm for traveling salesman problem,” Swarm and Evolutionary Computation, vol. 44, pp. 428–438, 2019. https://doi.org/10.1016/j.swevo.2018.05.006.
[15]E. F. Goldbarg, M. C. Goldbarg, and G. Souza, Particle Swarm Optimization Algorithm for the Traveling Salesman Problem. IntechOpen, 2008, pp. 75–96.
[16]H. A. Abdulkarim and I. F. Alshammari, “Comparison of algorithms for solving traveling salesman problem,” International Journal of Engineering and Advanced Technology (IJEAT), vol. 4(6), pp. 76–79, 2015.
[17]L. Wang, R. Cai, M. Lin, and Y. Zhong, “Enhanced list-based simulated annealing algorithm for large-scale traveling salesman problem,” IEEE Access, vol. 7, pp. 144 366–144 380, 2019. https://doi.org/10.1109/ACCESS.2019.2945570.
[18]B. Zarei and M. R. Metbodi, “A hybrid method for solving traveling salesman problem,” 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS), pp. 394–399, 2007. https://doi.org/10.1109/ICIS.2007.24.
[19]M. Rahbari and A. Jahed, “A hybrid simulated annealing algorithm for traveling salesman problem with three neighbor generation structures,” 10th International Conference of Iranian Operations Research Society (ICIORS), 2017. https://hal.science/hal-01962049v1.
[20]X. Geng, Z. Chen, W. Yang, D. Shi, and K. Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” Applied Soft Computing, vol. 11(4), pp. 3680–3689, 2011. https://doi.org/10.1016/j.asoc.2011.01.039.
[21]L. Xiong and S. Li, “Solving tsp based on the improved simulated annealing algorithm with sequential access restrictions,” Proceedings of the 2016 6th International Conference on Mechatronics, Computer and Education Informationization (MCEI 2016), vol. 130, pp. 610–616, 2016. https://doi.org/10.2991/mcei-16.2016.127.
[22]M. A. Rahman, A. Islam, and L. E. Ali, “Intelligent route construction algorithm for solving traveling salesman problem,” International Journal of Computer Science and Network Security, vol. 21, pp. 33–40, 2021. https://doi.org/10.22937/IJCSNS.2021.21.4.5.
[23]A. H. Zhou, L. P. Zhu, B. Hu, et al., “Traveling salesman problem algorithm based on simulated annealing and gene-expression programming,” Information, vol. 10(1), pp. 1–15, 2019. https://doi.org/10.3390/info10010007.
[24]I. Ilhan and G. Gokmen, “A list-based simulated annealing algorithm with crossover operator for the traveling salesman problem,” Nural Computing and Applications, vol. 34, pp. 7627–7652, 2022. DOI: https://doi.org/10.1007/s00521-021-06883-x.
[25]S. M. Chen and C. Y. Chien, “Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques,” Expert System with Applications, vol. 38(12), pp. 14 439–14 450, 2011. https://doi.org/10.1016/j.eswa.2011.04.163.
[26]J. Y. Potvin, “State-of-the-art survey—the traveling salesman problem: A neural network perspective,” ORSA Journal on Computing, vol. 5(4), pp. 328–348, 1993. https://doi.org/10.1287/ijoc.5.4.328.
[27]L. Paquete and T. Stutzle, “A two-phase local search for the biobjective traveling salesman problem,” Evolutionary Multi-Criterion Optimization, vol. 2632, pp. 479–493, 2003. https://doi.org/10.1007/3-540-36970-8_34.
[28]M. A. Rahman and H. Parvez, “Repetative nearest neighbor based simulated annealing search optimization algorithm for traveling salesman problem,” Open Access Library Journal, vol. 8(6), pp. 1–17, 2021. https://doi.org/10.4236/oalib.1107520.
[29]S. Emek, S. Bora, and A. Ugur, “Optimization of traveling salesman problem using genetic algorithm and fuzzy c-means clustering,” Global Journal on Technology, vol. 8, pp. 143–150, 2015. [Online]. Available: http://awer-center.org/gjt/.
[30]J. W. Yoon and S. B. Cho, “An efficient genetic algorithm with fuzzy c-means clustering for traveling salesman problem,” 2011 IEEE Congress of Evolutionary Computation (CEC), pp. 1452–1456, 2011. https://doi.org/10.1109/CEC.2011.5949786.
[31]G. E. A. Fuentes, E. S. H. Gress, J. C. S. T. Mora, and J. M. Marin, “Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic,” PLoS ONE, vol. 13(8), e0201868, 2018. https://doi.org/10.1371/journal.pone.0201868.
[32]A. Jaradat, B. Matalkeh, and W. Diabat, “Solving traveling salesman problem using firefly algorithm and k-means clustering,” 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT), pp. 586–589, 2019. https://doi.org/10.1109/JEEIT.2019.8717463.
[33]Y. Deng, Y. Lui, and D. Zhou, “An improved genetic algorithm with initial population strategy for symmetric tsp,” Mathematical Problems in Engineering, vol. 2015, p. 12 794, 2015. https://doi.org/10.1155/2015/212794.
[34]A. Elsamak andW. Ashour, “Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm,” Journal of Artificial Intelligence and Soft Computing Research, vol. 5(4), pp. 239–245, 2015. https://doi.org/10.1515/jaiscr-2015-0032.
[35]J. Martikainen and S. J. Ovaska, “Using fuzzy evolutionary programming to solve travelling salesman problem,” 9th IASTED International Conference on Artificial Intelligence and Soft Computing, pp. 49–54, 2005.
[36]J. Y. Potvin, “Genetic algorithms for the traveling salesman problem,” Annals of Operations Research, vol. 63, pp. 339–370, 1996. https://doi.org/10.1007/BF02125403.
[37]P. Larra˜naga, C. M. H. Kuijpers, R. 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. https://doi.org/10.1023/A:1006529012972.
[38]C. Chudasama, S. M. Shah, and M. Panchal, “Comparison of parents selection methods of genetic algorithm for tsp,” International Conference on Computer Communication and Networks CSI-COMNET, pp. 85–87, 2011.
[39]N. M. Razali and J. Geraghty, “Genetic algorithm performance with different selection strategies in solving tsp,” Proceedings of the World Congress on Engineering, vol. II, 2011.
[40]P. Y. Chen, C. H. Chen, and H. Wang, “A neural network: Family competition genetic algorithm and its applications in electromagnetic optimization,” Applied Computational Intelligence and Soft Computing, vol. 2009(1), pp. 474 125, 2009. https://doi.org/10.1155/2009/474125.
[41]Y. Wang, “The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem,” Computers Industrial Engineering, vol. 70, pp. 124–133, 2014. https://doi.org/10.1016/j.cie.2014.01.015.
[42]L. X. Wang, “The fuzzy c-means algorithm,” in A Course in Fuzzy System and Control. Prentice-Hall International, Inc, 1997, pp. 342–353.
[43]J. J. Grefenstette, R. Gopal, B. J. Rosmaita, and D. V. Gucht, “Genetic algorithms for the traveling salesman problem,” Proceedings of the 1st International Conference on Genetic Algorithms, ICGA’85, pp. 160–168, 1985.
[44]Tsplib, Accessed on 2024-11-17. [Online]. Available: http://comopt.ifi.uni- heidelberg.de/software/TSPLIB95.

International Journal of Intelligent Systems and Applications (IJISA)