## 1 Introduction  
Many complex real world problems can be formulated as combinatorial optimization (CO) problems. Technically, CO problems require a proper solution from a discrete finite set of feasible solutions in order to simultaneously achieve the minimization (or maximization) of a cost function and the satisfaction of the problem's given constraints. One such problem is finding the shortest path (or a path \"close\" to the shortest with respect to some appropriate metric) for a global positioning system (GPS) in a short period of time. The above real-world problem can be perfectly modeled by the travelling salesman problem (TSP). The travelling salesman problem (TSP) is one of the most widely studied combinatorial optimization problems. Solving the TSP means finding the minimum cost route so that the salesman (the person or entity who travels along a specific route containing many nodes) can start from a point of origin and return to the origin after passing from all given nodes once. The first use of the term \"travelling salesman problem\" appeared around 1931-1932. Remarkably, a century earlier, in 1832, a book was printed in Germany [1], which, although dedicated to other issues, in the last chapter deals with the essence of the TSP problem: \"With a suitable choice and route planning, you can often save so much time [making] suggestions [...]. The most important aspect is to cover as many locations [aspossible], without visiting a location [a] second time.\" In that book, the TSP is expressed for the first time using some examples of routes through Germany and Switzerland. However, an in-depth study of the problem is not attempted in this book. The TSP was expressed mathematically for the first time in the 19 th century by [PERSON] and [PERSON] [1]. A _cycle_ in a graph is a closed path that starts and ends at the same node and visits every other node exactly once. A cycle containing all vertices of the graph is called _Hamiltonian_. In short, TSP is the problem of finding the shortest Hamiltonian cycle. The Hamiltonian graph problem, i.e., deciding whether a graph has a Hamiltonian cycle, is reducible to the TSP. One can see this by assigning zero length to the edges of the graph and constructing a new edge of length, one for each missing edge. If the solution of the TSP for the resulting graph is zero, then the original graph contains a Hamiltonian cycle; if it is a positive number, then the original graph contains no Hamiltonian cycle [2]. TSP is NP-hard and is of great significance in various fields, such as operational research and theoretical computer science. In practice, TSP amounts to finding the best way one can visit all the cities, return to the starting point, and minimize the cost of the tour. Typically, TSP is represented by a graph. Specifically, the problem is stated in terms of a complete graph \(G=(V,A)\), in which \(V=\{v_{1},v_{2},\ldots,v_{n}\}\) is the set of nodes and \(A=\{(v_{i},v_{j}):v_{i},v_{j}\in V\) and \(v_{i}\
eq v_{j}\}\) is the set of the directed edges or arcs. Each arc is associated with a weight \(c_{ij}\) representing the cost (or the distance) of moving from node \(i\) to node \(j\). If \(c_{ij}\) is equal to \(c_{ji}\), the TSP is symmetric (sTSP); otherwise, it is called asymmetric (aTSP). The fact that TSP is NP-hard implies that there is no known polynomial-time algorithm for finding an optimal solution regardless of the size of the problem instance [3]. Real world problems, such as those related to GPS, can be formulated as instances of the TSP. This class of routing problems requires good solutions computed in a short amount of time. In order to improve the computational time, it is common practice to sacrifice some of the solution's quality by adopting heuristic and metaheuristic approaches [4; 5; 6]. Heuristics are fast approximation computational methods divided into construction and improvement heuristics. Construction heuristics are used to build feasible initial solutions, and improvement heuristics are applied to achieve better solutions.