THE STUDY OF THE INFLUENCE OF ASYMMETRY ON THE COMPLEXITY OF SOLVING THE TRAVELING SALESMAN PROBLEM BY THE BRANCH AND BOUND METHOD

Abstract

The traveling salesman problem is the one of the most famous combinatorial optimization problems. This problem is important and at the same time difficult to solve, due to the exponential complexity of the exact methods of solution. It occurs in an extensive class of applications: in the construction of optimal motion schemes, recognition of tracks and images. However, a number of scientific studies, in particular, genetics and bioinformatics, require an accurate solution. This study is concerned with the problem of asymmetry influence on the complexity of the solution, which obtained with the classical implementation of branches and bounds method. Since the study requires the analysis of numerous experimental data, there is a need to increase the speed of calculations. The selected approach using branch and bounds method allows gaining an extra speed of search in decision tree by maintaining in-memory state of the active list nodes of the tree. The efficiency of the implementation of the algorithm is also affected by the choice of data structures for the rapid finding of the next vertex under consideration. Based on the results and the analysis, the dependence of the complexity of the problem solution on the asymmetry of the matrix is established. Some asymmetry options reduce the complexity of the solution. The study of the influence of asymmetry on the traveling salesman problem’s complexity on the example of the classical solution algorithm – the method of branches and bounds – is of interest to further predictive analysis of the complexity of individual problems.

Keywords

• asymmetric traveling salesman problem
• branch and bound method
• data structures
• de-cision tree
• decision tree