Synthesis of algorithms of clustering to solve the multi-agent traveling salesman problem

Purpose of work. For a given (partially, completely) complex network, it is necessary to find, consistent with the routing problem, the network layout for a certain number of clusters, which provides high accuracy and speed of solving the corresponding extreme problems on the graphs.

The article considers graph clustering algorithms, as well as their application for discrete optimization problems on graphs, as an example of the problem for k traveling salesmen. The basic algorithms for solving the traveling salesman problem and some of their modifications are considered. On the basis of theoretical results the software implementation of the following clustering algorithms is developed: hierarchical algorithm, K-means and greedy algorithm with various modifications. A genetic algorithm for solving the traveling salesman problem was implemented, as well as the synthesis of clustering algorithms and the solution of the traveling salesman problem with finding the optimal centers.

The main task of the work was to find the optimal clusters or subgraphs of the desired graph, taking into account the uniform distribution of traveling salesman routes in clusters. As a result, the difference between splitting the graph into clusters (with the preservation of the required centers in these clusters) and finding the optimal centers for further clustering with them is demonstrated. To find optimal in relation to the problem k traveling salesmen subgraphs, a synthesis of clustering algorithms and solutions of discrete optimization problems was developed and implemented on the example of the traveling salesman problem for k agents. The essence of the method is the mechanism of "throwing" vertices from larger clusters to smaller ones, until the convergence condition is fulfilled, the objective function of which depends on the length of the traveling salesmen paths. There are various options for this mechanism, including the transit of vertices through clusters between large and small clusters, so that the resulting clusters do not lose compactness and do not create intersections in further search of the optimal route.