Study on Dependencies of Complexity of Asymmetric TSP Based on Values of Cycle Parameters of the Reduced Matrix

The work is devoted to forecasting for polynomial time the time costs for solving asymmetric traveling salesman tasks. In particular, characteristic functions that can correlate with time resources are studied. In order to measure the time spent on solving the problem objectively, the complexity of the individual problem is applicable - the term introduced by D. Knuth in 1974. In order to solve problem, a program is implemented that calculates the cycle parameters for the input data and correlation coefficients. The purpose of this paper is to investigate the characteristics of cycles of the reduced matrix to study the possible dependence on the TSP complexity. The object of the study is the individual traveling salesman tasks, as well as their complexity, obtained by counting the number of generated vertices in the search tree compiled as a result of the branch and bound algorithm work. The subject of the study are the correlation coefficients of the values of the reduced matrix cycles parameters and its complexity. The work includes 34 pages, 3 chapters, 4 figures, 3 tables, 19 sources, 8 applications. Key words — traveling salesman problem, branch and bound method, TSP complexity, cycles of reduced matrix, correlation coefficients.