Solving Traveling Salesman Problem Art Using Clustered Traveling Salesman Problem - Sulistia, Nadya; Irwansyah, Irwansyah; Marwan, Marwan ((IJCSAM) International Journal of Computing Science and Applied Mathematics, 2025)
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.