Solving Traveling Salesman Problem Art Using Clustered Traveling Salesman Problem - Nadya Sulistia; Irwansyah Irwansyah; Marwan Marwan (LPPM Institut Teknologi Sepuluh Nopember, 2025)
Abstract—The Traveling Salesman Problem (TSP) is a wellknownoptimization problem that seeks to determine the shortestpossible route that allows a salesman to visit each city exactlyonce before returning to the starting point. With advances in TSPtheory and its applications, a novel concept known as TSP Art hasemerged, blending mathematics with artistic expression. In TSPArt, the optimal solution to the TSP generates an artistic patternor figure. However, the complexity of this problem increases withthe number of vertices, making it computationally challengingto solve. This study proposes an approach using the ClusteredTraveling Salesman Problem (CTSP) to address the TSP Artproblem by organizing vertices into clusters, where each clusteris visited once, while maintaining an efficient overall tour. Theobjective of this research is to solve the TSP Art problemusing the CTSP approach and to calculate the length of theminimum tours. The Nearest Neighbor and 2-opt algorithms areapplied within each cluster to find the shortest paths, whileKruskal’s algorithm is employed to connect these paths intoan optimized overall tour. The minimum tour lengths for TSPArt representations of Mona Lisa, Van Gogh, and Venus aredetermined to be 6, 932, 014.19, 6, 878, 519.41, and 8, 210, 589.60distance unit, respectively.