Clustering of situations in the algorithms for solving the traveling salesman problem and its application in some applied tasks. Part II. List metrics and some related optimization problems

Background. In discrete optimization problems, we consider decision algorithms based on extensions of the branch and boundary method. These extensions themselves consist in the joint work of several auxiliary heuristic algorithms, and they can be attributed to different, independent of each other, areas of artificial intelligence. Therefore, the relevance of the research is provided both by subject areas and algorithms, i.e. the study of the joint work of various auxiliary algorithms related to different areas of AI. The goal is the further description of the application of clustering situations in the branch and bound method by the example of the traveling salesman problem. Materials and methods. The paper uses heuristic algorithms of artificial intelligence and discrete optimization, combined into a single software package, as well as statistical methods for analyzing algorithms. Results. The results are the regularities obtained with the application of clustering situations and some other heuristics in the method of branches and boundaries in solving the traveling salesman problem. Conclusions. It was proposed to improve the algorithm of branches and boundaries by connecting a heuristic to it for clustering situations. In addition, specific values were obtained for the relative improvement in the average time of operation of this algorithm in the applied problem considered by us, which is a version of the traveling salesman problem close to the pseudo-geometric one.