Solving Traveling Salesman Problem Art Using Clustered Traveling Salesman Problem
DOI:
https://doi.org/10.12962/j24775401.ijcsam.v11i1.4311Keywords:
Terms—Clustered Traveling Salesman Problem, Kruskal’s Algorithm, Nearest Neighbor Algorithm, TSP ArtAbstract
Abstract—The Traveling Salesman Problem (TSP) is a wellknown
optimization problem that seeks to determine the shortest
possible route that allows a salesman to visit each city exactly
once before returning to the starting point. With advances in TSP
theory and its applications, a novel concept known as TSP Art has
emerged, blending mathematics with artistic expression. In TSP
Art, the optimal solution to the TSP generates an artistic pattern
or figure. However, the complexity of this problem increases with
the number of vertices, making it computationally challenging
to solve. This study proposes an approach using the Clustered
Traveling Salesman Problem (CTSP) to address the TSP Art
problem by organizing vertices into clusters, where each cluster
is visited once, while maintaining an efficient overall tour. The
objective of this research is to solve the TSP Art problem
using the CTSP approach and to calculate the length of the
minimum tours. The Nearest Neighbor and 2-opt algorithms are
applied within each cluster to find the shortest paths, while
Kruskal’s algorithm is employed to connect these paths into
an optimized overall tour. The minimum tour lengths for TSP
Art representations of Mona Lisa, Van Gogh, and Venus are
determined to be 6, 932, 014.19, 6, 878, 519.41, and 8, 210, 589.60
distance unit, respectively.
References
[1] J. A. Bondy and U. S. R. Murty, Graph theory. Springer Publishing
Company, Incorporated, 2008.
[2] D. S. Johnson and L. A. McGeoch, “The traveling salesman problem: a
case study,” Local search in combinatorial optimization, pp. 215–310,
1997.
[3] K. Honda, Y. Nagata, and I. Ono, “A parallel genetic algorithm with edge
assembly crossover for 100,000-city scale tsps,” in 2013 IEEE congress
on evolutionary computation. IEEE, 2013, pp. 1278–1285.
[4] Y. Lu, J.-K. Hao, and Q. Wu, “Solving the clustered traveling salesman
problem via tsp methods,” arXiv preprint arXiv:2007.05254, 2020.
[5] H. Xu and H. Lan, “An adaptive layered clustering framework with
improved genetic algorithm for solving large-scale traveling salesman
problems,” Electronics, vol. 12, no. 7, p. 1681, 2023.
[6] B. A. AlSalibi, M. B. Jelodar, and I. Venkat, “A comparative study
between the nearest neighbor and genetic algorithms: A revisit to the
traveling salesman problem,” International Journal of Computer Science
and Electronics Engineering (IJCSEE), vol. 1, no. 1, pp. 110–123, 2013.
[7] K. Salahddine et al., “The implementation of kruskal’s algorithm for
minimum spanning tree in a graph,” in E3S Web of Conferences, vol.
297. EDP Sciences, 2021, p. 01062.
[8] H. A. Taha and H. A. Taha, Operations research: an introduction.
Prentice hall Upper Saddle River, NJ, 2003, vol. 7.
[9] R. Bosch and A. Herman, “Continuous line drawings via the traveling
salesman problem,” Operations research letters, vol. 32, no. 4, pp. 302–
303, 2004.
[10] A. Agrawal and H. Gupta, “Global k-means (gkm) clustering algorithm:
a survey,” International journal of computer applications, vol. 79, no. 2,
2013.
[11] D. Sharifrazi, R. Alizadehsani, J. H. Joloudari, S. S. Band, S. Hussain,
Z. A. Sani, F. Hasanzadeh, A. Shoeibi, A. Dehzangi, M. Sookhak et al.,
“Cnn-kcl: Automatic myocarditis diagnosis using convolutional neural
network combined with k-means clustering,” Mathematical Biosciences
and Engineering, vol. 19, no. 3, pp. 2381–2402, 2022.
[12] C. Shi, B. Wei, S. Wei, W. Wang, H. Liu, and J. Liu, “A quantitative
discriminant method of elbow point for the optimal number of clusters
in clustering algorithm,” Eurasip Journal on Wireless Communications
and Networking, vol. 2021, pp. 1–16, 2021.
[13] A. Sucipto, “Klasterisasi calon mahasiswa baru menggunakan algoritma
k-means,” Science Tech: Jurnal Ilmu Pengetahuan dan Teknologi, vol. 5,
no. 2, pp. 50–56, 2019.
[14] P. Bholowalia and A. Kumar, “Ebk-means: A clustering technique
based on elbow method and k-means in wsn,” International Journal
of Computer Applications, vol. 105, no. 9, 2014.
