### Book chapter

## Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)

It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.

### In book

The article is devoted to a new generic representation of classes of particular travelling salesman problems (TSP), we call it "index number matrix". This representation is intended for a separation of problem classes of similar complicity. This result is destined to solve a problem of particular TSP’s complicity prediction. Two hypotheses are given regarding to an appliance of the representation, that is proposed in the article. A method of index number matrix construction is also given. Some results are obtained by experiments, which didn’t interfere with one of our hypotheses.

The classical Branch and Bound algorithm for the travelling salesman problem, presented in 1963 by Little J.D.C., Murty K.G., Sweeney D.W., Karel C., is nowadays one of the most popular algorithms to find a minimum Hamiltonian cycle in a complete graph. There are many literature references having an algorithm pseudocode with comments. However, there are some special cases which are not discussed in these references. One of these cases is an-alyzedin this article.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.

In this paper a branch-and-bound algorithm for the Symmetric Travelling Salesman Problem (STSP) is presented. The algorithm is based on the 1-tree Lagrangian relaxation. A new branching strategy is suggested in which the algorithm branches on the 1-tree edge belonging to the vertex with maximum degree in the 1-tree and having the maximum tolerance. This strategy is compared with} branching on the shortest edge and the so-called strong branching, which is the branching on the edge with maximum tolerance also applied by Held & Karp (1971). The computational experiments show that {proposed} branching strategy provides better results on TSPlib benchmark instances.

The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these three types of cost functions we extend this theory from single to set tolerances and the related reverse set tolerances. In particular, we characterize specific values of (reverse) set upper and lower tolerances as positive and infinite, and we present a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present formulas or bounds for computing (reverse) set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. Finally, we give formulas for the minimum and maximum (reverse) set upper and lower tolerances using again their corresponding single tolerance counterparts.

For practical, important tasks in the fi elds of economics and logistics, as well as in a number of technical applications, it becomes necessary to solve the traveling salesman problem (TSP). Quite often, the features of these problems lead to the traveling salesman problem in asymmetric formulation (asymmetric traveling salesman problem, ATSP). Moreover, in some practical applications it is desirable to obtain an exact solution. One of the known exact algorithms for solving the ATSP is an algorithm that implements the well-known branch and bound method. The known experimental estimates of its complexity on the average are exponential. However, this does not mean that for small dimensions of the problem (currently, no more than 70–75), the expected time for solving the individual problem is unacceptably high. The need to reduce the time for solving individual problems dictated by practice is associated with the use of various modifi cations of this algorithm, of which a modifi cation that involves storing truncated matrices in the search decision tree is one of the most eff ective. In this article, the authors rely on this modifi cation. Other possible improvements in the time effi ciency of the software implementation of the branch and bound method are related, among other things, to obtaining the initial approximation by heuristic algorithms. As a result, we get a combined algorithm, in which, at the fi rst stage, some heuristics works to obtain the initial solution, from which the branch and bound method starts. This idea has been discussed for a long time, but the problem is that to reduce time, such a heuristic algorithm is needed that delivers a solution close to optimal which will be found quite fast. One of the possible solutions to this problem is the subject of this article. The subject of the research in this article is the choice of the best heuristic algorithm which, when applied, leads to an increase in temporal effi ciency in combination with the algorithm of the branch and bound method, and an experimental study of its software implementation in order to obtain an average time for solving individual problems. On the basis of the results obtained, recommendations are given on the limiting dimensions of the problem that allow for an acceptable solution time, something which is of interest in the practical application of this combined algorithm in the tasks of business informatics and logistics.