## 1 Introduction  
The Traveling Salesman Problem (TSP) is one of the most studied strongly NP-hard combinatorial optimization problems. Given an \(n\times n\) matrix of distances between \(n\) objects, call them cities, one looks for a shortest possible feasible tour which can be seen as a permutation of the given \(n\) objects: a feasible tour visits each of the \(n\) cities exactly once except the first visited city with which the tour ends. The cost of a tour is the sum of the distances between each pair of the neighboring cities in that tour. This problem can also be described in graph terms. We have an undirected weighted complete graph \(G=(V,E)\), where \(V\) is the set of \(n=|V|\) vertices (cities) and \(E\) is the set of the \(n^{2}-n\) edges \((i,j)=(j,i)\
eq j\). A non-negative weight of an edge \((i,j)\), \(w(i,j)\) is the distance between vertices \(i\) and \(j\). There are two basic sets of restrictions that define feasible solution (a tour that has to start and complete at the same vertex and has to contain all the vertices from set \(V\) exactly once). A feasible tour \(T\) can be represented as:\[T=(i_{1},i_{2},\cdots,i_{n-1},i_{n},i_{1})\text{; }i_{k}\in V\text{,} \tag{1}\]  
and its cost is  
\[C(T)=\sum_{k=1}^{n-1}w(i_{k},i_{k+1})+w(i_{n},i_{1})\text{.} \tag{2}\]  
The objective is to find an _optimal_ tour, a feasible one with the minimum cost \(\min_{T}\ C(T)\). Some special cases of the problem have been commonly considered. For instance, in the symmetric version, the distance matrix is symmetric (i.e., for each edge \((i,j)\), \(w(i,j)=w(j,i)\)); in another setting, the distances between the cities are Euclidean distances (i.e., set \(V\) can be represented as points in the two-dimensional Euclidean space). Clearly, the Euclidean TSP is also a symmetric TSP but not vice versa. The Euclidean TSP has a straightforward immediate application in the real-life scenario when a salesman wishes to visit the cities using the shortest possible tour. Because in the Euclidean version the cities are points in plane, for each pair of points, the triangle inequality holds, which makes the problem a bit more accessible in the sense that simple geometric rules can be used for calculating the cost of a tour or the cost of the inclusion of a new point in a partial tour, unlike the general setting. Nevertheless, the Euclidean TSP remains strongly NP-hard; see [PERSON] (2016) and [PERSON] et al. (2018). The exact solution methods for TSP can only solve problem instances with a moderate number of cities; hence, approximation algorithms are of a primary interest. There exist a vast amount of approximation heuristic algorithms for TSP. The literature on TSP is very wide-ranging, and it is not our goal to overview all the important relevant work here (we refer the reader, e.g., to a book by [PERSON] et al. (2017) and an overview chapter by [PERSON] (2018)). The literature distinguishes two basic types of approximation algorithms for TSP: tour construction and loop improvement algorithms. The construction heuristics create a feasible tour in one pass so that the taken decisions are not reconsidered later. A feasible solution delivered by a construction heuristic can be used in a loop improvement heuristic as an initial feasible solution (though such initial solution can be constructed randomly). Given the current feasible tour, iteratively, an improvement algorithm, based on some local optimality criteria, makes some changes in that tour resulting in a new feasible solution with less cost. Well-known examples of tour improvement algorithms are _2-Opt_ Crees _2-Opt_, its generalizations _3-Opt_ and _k-Opt_, and the algorithm by [PERSON] and [PERSON] (2017), to mention a few. The most successful algorithms we have found in the literature for large-scale TSP instances are Ant Colony Optimization (ACO) meta heuristics, with which we compare our results. On one hand, these algorithms give a good approximation.