Аналіз швидкодії методу k-means для декомпозиції задачі комівояжера великих розмірностей

Abstract

Декомпозиція задачі базується на кластеризації вхідної множини точок відомим методом k-means та алгоритмі розширення часткового розв’язку у кластерах. Саме k-means застосовано для поділу множини вхідних даних для задачі комівояжера великих розмірностей на менші підзадачі. Обгрунтовано доцільність його використання для зменшення розмірності. На основі проведених експериментів запропоновано застосування ієрархічної версії алгоритму для задач розмірністю більше мільйона точок, проаналізовано доцільність застосування алгоритму k-means для відомих тестових задач комівояжера великих та дуже великих розмірностей. Вхідними даними служать задачі з колекцій TSPLIB та DIMACS TSP Challenge. Проведено експерименти для задач розмірністю від 100 тисяч до 10 мільйонів точок. Згідно з одержаними результатами експериментів (час роботи алгоритму кластеризації задачі на 10 мільйонів точок становить трохи більше 8 хвилин), зроблено висновок про можливість застосування такої кластеризації для декомпозиції задачі. 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.