Abstract

The Travelling Salesman Problem (TSP), which is a combinatorial NP-hard problem, aims to find the shortest possible path while visiting all cities (only once) in a given list and returns to the starting point. In this paper, an approach, which is based on k-means clustering and Shuffled Frog Leaping Algorithm (SFLA), is used to solve the TSP. The proposed approach consists of three parts: separate the cities into k clusters, find the shortest path for each cluster and merge the clusters. Experimental results have shown that the algorithm get better results as the number of cluster increase for problems that have a large number of cities.

References

[1] A. H. Halim and I. Ismail, "Combinatorial optimization: comparison of heuristicalgorithms in travelling salesman problem," Archives of Computational Methods inEngineering, vol. 26, pp. 367-380, 2019.
[2] C. K. Joshi, T. Laurent, and X. Bresson, "An Efficient Graph Convolutional NetworkTechnique for the Travelling Salesman Problem," arXiv preprint arXiv:1906.01227,2019.
[3] S. S. Juneja, P. Saraswat, K. Singh, J. Sharma, R. Majumdar, and S. Chowdhary,"Travelling Salesman Problem Optimization Using Genetic Algorithm," in 2019 AmityInternational Conference on Artificial Intelligence (AICAI), 2019, pp. 264-268.
[4] K. Chaudhari and A. Thakkar, "Travelling Salesman Problem: An Empirical ComparisonBetween ACO, PSO, ABC, FA and GA," in Emerging Research in Computing,Information, Communication and Applications, ed: Springer, 2019, pp. 397-405.
[5] A. Hatamlou, "Solving travelling salesman problem using black hole algorithm," SoftComputing, vol. 22, pp. 8167-8175, 2018.
[6] Y. Saji and M. E. Riffi, "A novel discrete bat algorithm for solving the travellingsalesman problem," Neural Computing and Applications, vol. 27, pp. 1853-1866, 2016.
[7] R. Gupta, N. Shrivastava, M. Jain, V. Singh, and A. Rani, "Greedy WOA for TravellingSalesman Problem," in International Conference on Advances in Computing and DataSciences, 2018, pp. 321-330.
[8] E. L. Lawler, J. K. Lenstra, A. H. Rinnooy Kan, and D. B. Shmoys, "The travelingsalesman problem; a guided tour of combinatorial optimization," 1985.
[9] V. Tongur and E. Ülker, "The analysis of migrating birds optimization algorithm withneighborhood operator on traveling salesman problem," in Intelligent and EvolutionarySystems, ed: Springer, 2016, pp. 227-237.
[10] TSPLIB. (2019, 02 Sep.). TSP Library Benchmarks. Available: http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html
[11] J. MacQueen, "Some methods for classification and analysis of multivariateobservations," in Proceedings of the fifth Berkeley symposium on mathematical statisticsand probability, 1967, pp. 281-297.
[12] M. Capó, A. Pérez, and J. A. Lozano, "An efficient approximation to the K-meansclustering for massive data," Knowledge-Based Systems, vol. 117, pp. 56-69, 2017.
[13] P. Arora and S. Varshney, "Analysis of k-means and k-medoids algorithm for big data,"Procedia Computer Science, vol. 78, pp. 507-512, 2016.
[14] M. KARAKOYUN, A. SAGLAM, N. A. BAYKAN, and A. A. ALTUN, "Non-locallycolor image segmentation for remote sensing images in different color spaces by usingdata-clustering methods," image, vol. 10, p. 11, 2017.
[15] T. Velmurugan, "Performance based analysis between k-Means and Fuzzy C-Meansclustering algorithms for connection oriented telecommunication data," Applied SoftComputing, vol. 19, pp. 134-146, 2014.
[16] M. M. Eusuff and K. E. Lansey, "Optimization of water distribution network design usingthe shuffled frog leaping algorithm," Journal of Water Resources planning andmanagement, vol. 129, pp. 210-225, 2003.
[17] M. Karakoyun and A. Babalik, "Data clustering with shuffled leaping frog algorithm(SFLA) for classification," in International Conference on Intelligent Computing,Electronics Systems and Information Technology (ICESIT 2015), 2015, pp. 25-26.
[18] V. K. Jonnalagadda and V. K. D. MALLESHAM, "Bidding strategy of generationcompanies in a competitive electricity market using the shuffled frog leaping algorithm,"Turkish Journal of Electrical Engineering & Computer Sciences, vol. 21, pp. 1567-1583,2013.
[19] M. Eusuff, K. Lansey, and F. Pasha, "Shuffled frog-leaping algorithm: a memetic metaheuristic for discrete optimization," Engineering optimization, vol. 38, pp. 129-154, 2006.
[20] V. Jarník, "O jistém problému minimálním," Práca Moravské PrírodovedeckéSpolecnosti, vol. 6, pp. 57-63, 1930.
[21] R. C. Prim, "Shortest connection networks and some generalizations," The Bell SystemTechnical Journal, vol. 36, pp. 1389-1401, 1957.
[22] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerischemathematik, vol. 1, pp. 269-271, 1959.