Study of the effectiveness of applying the k-means method to decompose large-scale traveling salesman problems

The decomposition of the problem is based on clustering the input set of points using the well-known k- means method, combined with an algorithm for extending partial solutions within clusters. k-means clustering algorithm is examined for partitioning the input data set of large-scale TSP instances into smaller subproblems. The efficiency of using it to reduce problem size is substantiated. Based on experiments, the application of a hierarchical version of the algorithm is proposed for problems with more than one million points. The paper analyzes the feasibility of using the k-means algorithm for well-known large and huge TSP test instances. The well-known collections of TSP instances (TSPLIB and the DIMACS TSP Challenge) are investigated. Experiments were conducted for problems ranging from 100 thousand to 10 million points. According to the experimental results (the clustering algorithm’s runtime for a 10- million-point problem is slightly over 8 minutes), it was concluded that such clustering could indeed be used for problem decomposition. A hierarchical version of k-means clustering has been developed for very large-scale problems.