1. SISN
  2. All Volumes and Issues
  3. Volume 17, 2025
  4. Study of the Effectiveness of Applying the K-Means Method to Decompose Large-Scale Traveling Salesman Problems

Study of the Effectiveness of Applying the K-Means Method to Decompose Large-Scale Traveling Salesman Problems

SISN.
2025;
Volume 17
: pp. 138 - 145
https://doi.org/10.23939/sisn2025.17.138
Authors:
  1. Roman Kutelmakh
1
Lviv Polytechnic National University, Department of Software, Lviv, Ukraine

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.

clustering
algorithm
large scale
k-means
traveling salesman problem
subproblem
graph partitioning
  1. 1,331,906,450 stars Gaia DR2 (2023). https://www.math.uwaterloo.ca/tsp/star/gaia2.html
  2. Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The traveling salesman problem: A computational study.Princeton University Press.
  3. Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms (pp. 1027–1035). Society for Industrial and Applied Mathematics.
  4. Bentley, J. L. (1990). Experiments on traveling salesman heuristics. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (pp. 91–99).
  5. Bosch R. (2022), Opt Art. From mathematical optimization to visual design. Kharkiv. Fabula.
  6. Darte, A., & Vivien, F. (1995). Revisiting the decomposition of Karp, Miller, and Winograd. Parallel Processing Letters, 5(1), 13–25. https://doi.org/10.1109/ASAP.1995.522901
  7. DIMACS TSP Challenge (2001). http://archive.dimacs.rutgers.edu/Challenges/TSP/
  8. Drori, I., Kates, B. J., Sickinger, W. R., Kharkar, A. G., Dietrich, B., Shporer, A., & Udell, M. (2020). GalaxyTSP: A new billion-node benchmark for TSP. In Proceedings of the 1st Workshop on Learning Meets Combinatorial Algorithms @ NeurIPS 2020 (pp. 1–7). Vancouver, Canada.
  9. Fränti, P., & Virmajoki, O. (2006). Iterative shrinking method for clustering problems. Pattern Recognition, 39(5), 761–775.
  10. Gagolewski, M., Cena, A., Bartoszuk, M., & Brzozowski, L. (2024). Clustering with minimum spanning trees: How good can it be? Journal of Classification, 1–23. https://doi.org/10.1007/s00357-024-09483-1
  11. Guibas, L. J., & Stolfi, J. (1985). Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2), 75–123.
  12. Jothi, R., Mohanty, S. K., & Ojha, A. (2018). Fast approximate minimum spanning tree based clustering algorithm. Neurocomputing, 272, 542–557. https://doi.org/10.1016/j.neucom.2017.07.038
  13. Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291–307. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
  14. Khamis, A. (2024). Optimization algorithms: AI techniques for design, planning, and control problems. Manning.
  15. KmeansPlusPlus (2017). GitHub. https://github.com/ieyjzhou/KmeansPlusPlus
  16. Kutelmakh, R. K. (2024). Solving NP-Hardness. Efficient Solution to the Traveling Salesman Problem (Prof. Balylevych R. P., Ed.). Lviv. Lviv Polytechnic Publishing House.
  17. Kutelmakh, R., Bazylevych, R., & Prasad, B. (2023). Solving large scale uniform traveling salesman problem by using partial solution expansion method. In 2023 IEEE 18th International Conference on Computer Science and Information Technologies (CSIT) (pp. 1–4). Lviv, Ukraine. https://doi.org/10.1109/CSIT61576.2023.10324172
  18. Mona Lisa TSP Challenge (2008). https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html
  19. Star Tours (2023). https://www.math.uwaterloo.ca/tsp/star/index.html
  20. Taillard, É., & Helsgaun, K. (2019). Popmusic for the travelling salesman problem.  European Journal of Operational Research, 272(2), 420–429. https://doi.org/10.1016/j.ejor.2018.06.039
  21. TSPLIB (1995). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/