ESTIMATION OF PERSPECTIVITY OF BRANCHES IN THE METHOD OF BRANCHES AND BORDERS WHEN SOLVING THE TRADITIONAL TRAFFIC TASK

Abstract

The article discusses the option of improving the efficiency of solving the traveling salesman problem by applying an extended branch estimate in the branch and bound method. The algorithm for as-sessing the «perspective» of some aij branch operates on the cost of the branches leaving node i and the branches included in node j. The algorithm considers the branches of zero length and selects the branch, with the replacement of which to infinity, you can subtract the largest number from the row and column cor-responding to this branch.

The algorithm considers the branches of zero length and selects the branch, with the replacement of which to infinity, you can subtract the largest number from the row and column corresponding to this branch. The branch estimate can be expanded, taking into account the greater number of elements of the cost matrix, namely, the branches included in node i, and the branches leaving node j, that is, the j row and i col-umn, thus doubling the number of analyzed elements of the matrix. The proposed extended estimate allows to increase the efficiency of the algorithm.
The work in the study of algorithms used the programming language C#. The efficiency of the algorithm increases with increasing dimension of the problem. The results of solving test tasks are given. The numeri-cal experiment showed that for problems with more than 300 cities, each solution using the extended esti-mate turns out to be better than using the classical algorithm, the probability of obtaining an improved solu-tion approaches 100 %.