Solving Traveling Salesman Problem Art Using Clustered Traveling Salesman Problem

Nadya Sulistia, Irwansyah Irwansyah, Marwan Marwan

Abstract


Traveling Salesman Problem (TSP) is a method of finding the minimum tour in a graph. In line with the development of TSP theory and its application, TSP Art shows up as the implementation of mathematics in art. TSP Art is an art which represented in a graph. TSP Art consists of a lot of vertice that make the solution more complicated to be found. This problem has been solved using the Parallel Genetic Algorithm with Edge Assembly Crossover algorithm (GA-EAX). However, there are few lacks of this algorithm e.g., the running time is too long, it needs $12$ hours to solve the problem. In addition, GA-EAX required too much amount of RAM to process hundreds thousands of these vertice. While, in this research, one of the TSP variants is used, that is Clustered Traveling Salesman Problem (CTSP). CTSP is a modification of TSP by clustering number of vertice in a cluster, where each cluster must be visited one by one. The purpose of this study is to determine the TSP Art's solution using the CTSP method and to know the length of the CTSP’s minimum tour on the TSP Art problem. In this study, the Nearest Neighbor Heuristic algorithm is used to find the minimum path of each cluster. Furthermore, Kruskal’s algorithm is used to connect those minimum paths to become CTSP’s minimum tour. Based on this study, the minimum tour of Monalisa, Van Gogh, and Venus are 6.932.014,192594253 distance units, 7.902.043,90173308 distance units, and 8.210.589,60220378 distance units, respectively.

Keywords


Clustered Traveling Salesman Problem, Kruskal’s Algorithm, Nearest Neighbor Heuristic Algorithm, TSP Art.

Full Text:

PDF

References


J. A. Bondy and U. S. R. Murty, Graph theory. Springer Publishing Company, Incorporated, 2008.

Y. Lu, J.-K. Hao, and Q. Wu, “Solving the clustered traveling salesman problem via tsp methods,” arXiv preprint arXiv:2007.05254, 2020.

H. A. Taha, “Operations research an introduction,” 2007.

R. Bosch and A. Herman, “Continuous line drawings via the traveling salesman problem,” Operations research letters, vol. 32, no. 4, pp. 302-303, 2004.

B. M. Metisen and H. L. Sari, “Analisis clustering menggunakan metode k-means dalam pengelompokkan penjualan produk pada swalayan fad-hila,” Jurnal media infotama, vol. 11, no. 2, 2015.

T. Alfina, B. Santosa, and A. R. Barakbah, “Analisa perbandingan metode hierarchical clustering, k-means dan gabungan keduanya dalam cluster data (studi kasus: Problem kerja praktek teknik industri its),” Jurnal teknik its, vol. 1, no. 1, pp. A521–A525, 2012.

A. Agrawal and H. Gupta, “Global k-means (gkm) clustering algorithm: a survey,” International journal of computer applications, vol. 79, no. 2, 2013.

D. Sharifrazi, R. Alizadehsani, J. H. Joloudari, S. Shamshirband, S. Hussain, Z. A. Sani, F. Hasanzadeh, A. Shoaibi, A. Dehzangi, and H. Alinejad-Rokny, “Cnn-kcl: Automatic myocarditis diagnosis using convolutional neural network combined with k-means clustering,” 2020.

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.

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.

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.




DOI: http://dx.doi.org/10.12962/j24775401.v11i1.20259

Refbacks

  • There are currently no refbacks.



View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.