Introduction

The Traveling Salesman Problem (TSP) is one of the most representative problems in combinatorial optimization. If we consider a salesman who has to visit n cities [46], the Traveling Salesman Problem asks for the shortest tour through all the cities such that no city is visited twice and the salesman returns at the end of the tour back to the starting city. Mathematically, the problem may be stated as follows: Let \( G=(V,\,E) \) be a graph, where V is a set of n nodes and E is a set of arcs, let \( C=[c_{ij}] \) be a cost matrix associated with E, where c ij represents the cost of going from city i to city j, \( (i,\,j = 1,\,\ldots\,,\, n) \), the problem is to find a permutation (\( i_1,\,i_2,\,i_3,\,\ldots\,,\,i_n) \) of the integers from 1 through n that minimizes the quantity \( c_{i_1i_2}+c_{i_2i_3}+\ldots+c_{i_ni_1} \).

We speak of a  Symmetric TSP , if for all pairs (i, j), the distance c ij is equal to the distance c ji . Otherwise, we speak of the Asymmetric TSP  [7]. If the triangle inequality holds \( (c_{ij}\leq c_{ii_1} + c_{i_1j},\,\forall i,\,j,\, i_1 \)), the problem is said to be metric. If the cities can be represented as points in the plain such that c ij is the Euclidean distance between point i and point j, then the corresponding TSP is called the Euclidean TSP. Euclidean TSP obeys in particular the triangle inequality \( c_{ij} \leq c_{ii_1} + c_{i_1j} \) for all \( i,\,j,\,i_1 \).

An integer programming formulation of the Traveling Salesman Problem is defined in a complete graph \( G=(V,E) \) of n nodes, with node set \( V =\{1,\,\ldots\,,\,n \} \), arc set \( E = \{(i,\,j) | i,\,j = 1,\,\ldots\,,\,n \} \), and nonnegative costs c ij associated with the arcs [8]:

$$ c^{*} = \min \sum_{i \in V} \sum_{j \in V}c_{ij}x_{ij} $$
(1)
$$ \begin{aligned} &\text{s.t.} \\ &\sum_{j \in V}x_{ij} = 1,\quad i \in V \end{aligned} $$
(2)
$$ \sum_{i \in V} x_{ij} = 1,\quad j \in V $$
(3)
$$ \sum_{i \in S}\sum_{j \in S}x_{ij} \leq |S| - 1,\quad \forall S \subset V,\,S \neq \emptyset $$
(4)
$$ x_{ij} \in \{0,\,1\},\quad \text{for all}\; i,\,j \in V\:, $$
(5)

where \( x_{ij} = 1 \) if arc (i, j) is in the solution and 0 otherwise. In this formulation, the objective function clearly describes the cost of the optimal tour. Constraints (2) and (3) are degree constraints: they specify that every node is entered exactly once and left exactly once. Constraints (4) are subtour elimination constraints. These constraints prohibit the formation of subtours, i. e. tours on subsets of less than V nodes. If there was such a subtour on a subset S of nodes, this subtour would contain \( |S| \) edges and as many nodes. Constraints (4) would then be violated for this subset since the left-hand side of (4) would be equal to \( |S| \) while the right-hand side would be equal to \( |S|-1 \). Because of degree constraints, subtours over one node (and hence, over \( n-1 \) nodes) cannot occur. For more formulations of the problem see [34,60].

The Traveling Salesman Problem (TSP) is one of the most famous hard combinatorial optimization problems. It has been proven that TSP is a member of the set of NP-complete problems. This is a class of difficult problems whose time complexity is probably exponential. The members of the class are related so that if a polynomial time algorithm was found for one problem, polynomial time algorithms would exist for all of them [41]. However, it is commonly believed that no such polynomial algorithm exists. Therefore, any attempt to construct a general algorithm for finding optimal solutions for the TSP in polynomial time must (probably) fail. That is, for any such algorithm it is possible to construct problem instances for which the execution time grows at least exponentially with the size of the input. Note, however, that time complexity here refers to the worst case behavior of the algorithm. It can not be excluded that there exist algorithms whose average running time is polynomial. The existence of such algorithms is still an open question. Since 1950s many algorithms have been proposed, developed and tested for the solution of the problem. Algorithms for solving the TSP may be divided into two categories, exact algorithms and heuristic–metaheuristic algorithms .

Heuristics for the Traveling Salesman Problem

There is a great need for powerful heuristics that find good suboptimal solutions in reasonable amounts of computing time. These algorithms are usually very simple and have short running times. There is a huge number of papers dealing with finding near optimal solutions for the TSP. Our aim is to present the most interesting and efficient algorithms and the most important ones for facing practical problems. In the 1960s, 1970s and 1980s the attempts to solve the Traveling Salesman Problem focused on tour construction methods and tour improvement methods. In the last fifteen years, metaheuristics, such as simulated annealing, tabu search, genetic algorithms and neural networks, were introduced. These algorithms have the ability to find their way out of local optima. Heuristics and metaheuristics constitute an increasingly essential component of solution approaches intended to tackle difficult problems, in general, and global and combinatorial problems in particular.

When a heuristic is designed, the question which arises is about the quality of the produced solution. There are three different ways that one may try to answer this question.

  1. 1.

    Empirical. The heuristic is applied to a number of test problem instances and the solutions are compared to the optimal values, if there are known, or to lower bounds on these values [33,35].

  2. 2.

    Worst Case Analysis. The idea is to derive bounds on the worst possible deviation from the optimum that the heuristic could produce and to devise bad problem instances for which the heuristic actually achieves this deviation [42].

  3. 3.

    Probabilistic Analysis. In the probabilistic analysis it is assumed that problem instances are drawn from certain simple probability distributions, and it is, then, proven mathematically that particular solution methods are highly likely to yield near-optimal solutions when the number of cities is large [43].

Tour Construction methods build up a tour step by step. Such heuristics build a solution (tour) from scratch by a growth process (usually a greedy one) that terminates as soon as a feasible solution has been constructed. The problem with construction heuristics is that although they are usually fast, they do not, in general, produce very good solutions. One of the simplest tour construction methods is the nearest neighborhood in which, a salesman starts from an arbitrary city and goes to its nearest neighbor. Then, he proceeds from there in the same manner. He visits the nearest unvisited city, until all cities are visited, and then returns to the starting city [65,68].

An extension of the nearest neighborhood method is the double-side nearest neighborhood method where the current path can be extended from both of its endnodes. Some authors use the name Greedy for Nearest Neighborhood, but it is more appropriately reserved for the special case of the greedy algorithm of matroid theory [39]. Bentley [11] proposed two very fast and efficient algorithms, the K-d Trees and the Lazily Update Priority Queues. In his paper, it was the first time that somebody suggested the use of data structures for the solution of the TSP. A priority queue contains items with associated values (the priorities) and support operations that [40]:

  • remove the highest priority item from the queue and deliver it to the user,

  • insert an item,

  • delete an item, and

  • modify the priority of an item.

The insertion procedures [68] take a subtour of V nodes and attempt to determine which node (not already in the subtour) should join the subtour next (the selection step ) and then determine where in the subtour it should be inserted (the insertion step ). The most known of these algorithms is the nearest insertion algorithm. Similar to the nearest insertion procedure are the cheapest insertion [65], the arbitrary insertion [12], the farthest insertion [65], the quick insertion [12], and the convex hull insertion [12] algorithms.

There is a number of heuristic algorithms that are designed for speed rather for quality of the tour they construct [40]. The three most known heuristic algorithms of this category are the Strip algorithm, proposed by Beardwood et al. [10], the Spacefilling Curve proposed by Platzmann and Bartholdi [58] and the Fast Recursive Partitioning heuristic proposed by Bentley [11]. The saving algorithms are exchange procedures. The most known of them is the Clarke-Wright algorithm [17]. Christofides [12,65] suggested a procedure for solving the TSP based on spanning trees. He proposed a method of transforming spanning trees to Eulerian graphs.

The improvement methods or local search methods start with a tour and try to find all tours that are “neighboring” to it and are shorter than the initial tour and, then, to replace it. The tour improvements methods can be divided into three categories according to the type of the neighborhood that they use [64]. Initially, the constructive neighborhood methods, which successively add new components to create a new solution, while keeping some components of the current solution fixed. Some of these methods will be presented in the next section where the most known metaheuristics are presented. Secondly, the transition neighborhood methods, which are the classic local search algorithms (classic tour improvement methods) and which iteratively move from one solution to another based on the definition of a neighborhood structure. Finally, the population based neighborhood methods, which generalize the two previous categories by considering neighborhoods of more than one solution.

The most known of the local search algorithms is the 2-opt heuristic, in which two edges are deleted and the open ends are connected in a different way in order to obtain a new tour [48]. Note that there is only one way to reconnect the paths. The 3-opt heuristic is quite similar with the 2-opt but it introduces more flexibility in modifying the current tour, because it uses a larger neighborhood. The tour breaks into three parts instead of only two [48]. In the general case, δ edges in a feasible tour are exchanged for δ edges not in that solution as long as the result remains a tour and the length of that tour is less than the length of the previous tour. Lin-Kernighan method (LK) was developed by Lin and Kernighan [37,49,54] and for many years was considered to be the best heuristic for the TSP. The Or-opt procedure, well known as node exchange heuristic, was first introduced by Or [56]. It removes a sequence of up-to-three adjacent nodes and inserts it at another location within the same route. Or-opt can be considered as a special case of 3-opt (three arcs exchanges) where three arcs are removed and substituted by three other arcs. The GENI algorithm was presented by Gendreau, Hertz and Laporte [22]. GENI is a hybrid of tour construction and local optimization.

Metaheuristics for the Traveling Salesman Problem

The last fifteen years an incremental amount of metaheuristic algorithms have been proposed. Simulated annealing, genetic algorithms, neural networks, tabu search, ant algorithms, together with a number of hybrid techniques are the main categories of the metaheuristic procedures. These algorithms have the ability to find their way out of local optima. A number of metaheuristic algorithms have been proposed for the solution of the Traveling Salesman Problem. The most important algorithms published for each metaheuristic algorithm are given in the following:

  • Simulated Annealing (SA) belongs [1,2,45,64] to a class of local search algorithms that are known as threshold accepting algorithms . These algorithms play a special role within local search for two reasons. First, they appear to be quite successful when applied to a broad range of practical problems. Second, some threshold accepting algorithms such as SA have a stochastic component, which facilitates a theoretical analysis of their asymptotic convergence. Simulated Annealing [3] is a stochastic algorithm that allows random uphill jumps in a controlled fashion in order to provide possible escapes from poor local optima. Gradually the probability allowing the objective function value to increase is lowered until no more transformations are possible. Simulated Annealing owes its name to an analogy with the annealing process in condensed matter physics, where a solid is heated to a maximum temperature at which all particles of the solid randomly arrange themselves in the liquid phase, followed by cooling through careful and slow reduction of the temperature until the liquid is frozen with the particles arranged in a highly structured lattice and minimal system energy. This ground state is reachable only if the maximum temperature is sufficiently high and the cooling sufficiently slow. Otherwise a meta-stable state is reached. The meta-stable state is also reached with a process known as quenching, in which the temperature is instantaneously lowered. Its predecessor is the so-called Metropolis filter. Simulated Annealing algorithms for the TSP are presented in [15,55,65].

  • Tabu search (TS) was introduced by Glover [24,25] as a general iterative metaheuristic for solving combinatorial optimization problems. Computational experience has shown that TS is a well established approximation technique, which can compete with almost all known techniques and which, by its flexibility, can beat many classic procedures. It is a form of local neighbor search. Each solution S has an associated set of neighbors N(S). A solution \( S^{\prime} \in N(S) \) can be reached from S by an operation called a move. TS can be viewed as an iterative technique which explores a set of problem solutions, by repeatedly making moves from one solution S to another solution \( S^{\prime} \) located in the neighborhood N(S) of S [31]. TS moves from a solution to its best admissible neighbor, even if this causes the objective function to deteriorate. To avoid cycling, solutions that have been recently explored are declared forbidden or tabu for a number of iterations. The tabu status of a solution is overridden when certain criteria ( aspiration criteria ) are satisfied. Sometimes, intensification and diversification strategies are used to improve the search. In the first case, the search is accentuated in the promising regions of the feasible domain. In the second case, an attempt is made to consider solutions in a broad area of the search space. The first Tabu Search algorithm implemented for the TSP appears to be the one described by Glover [23,29]. Limited results for this implementation and variants on it were reported by Glover [26]. Other Tabu Search algorithms for the TSP are presented in [74].

  • Genetic Algorithms (GAs) are search procedures based on the mechanics of natural selection and natural genetics. The first GA was developed by John H. Holland in the 1960s to allow computers to evolve solutions to difficult search and combinatorial problems, such as function optimization and machine learning [38]. Genetic algorithms offer a particularly attractive approach for problems like traveling salesman problem since they are generally quite effective for rapid global search of large, non-linear and poorly understood spaces. Moreover, genetic algorithms are very effective in solving large-scale problems. Genetic algorithms mimic the evolution process in nature. GAs are based on an imitation of the biological process in which new and better populations among different species are developed during evolution. Thus, unlike most standard heuristics, GAs use information about a population of solutions, called individuals, when they search for better solutions. A GA is a stochastic iterative procedure that maintains the population size constant in each iteration, called a generation. Their basic operation is the mating of two solutions in order to form a new solution. To form a new population, a binary operator called crossover, and a unary operator, called mutation, are applied [61,62]. Crossover takes two individuals, called parents, and produces two new individuals, called offsprings, by swapping parts of the parents. Genetic algorithms for the TSP are presented in [9,51,59,64,67].

  • Greedy Randomized Adaptive Search Procedure - GRASP [66] is an iterative two phase search method which has gained considerable popularity in combinatorial optimization. Each iteration consists of two phases, a construction phase and a local search procedure. In the construction phase, a randomized greedy function is used to build up an initial solution. This randomized technique provides a feasible solution within each iteration. This solution is then exposed for improvement attempts in the local search phase. The final result is simply the best solution found over all iterations. Greedy Randomized Adaptive Search Procedure algorithms for the TSP are presented in [50,51].

  • The use of Artificial Neural Networks to find good solutions to combinatorial optimization problems has recently caught some attention. A neural network consists of a network [57] of elementary nodes (neurons) that are linked through weighted connections. The nodes represent computational units, which are capable of performing a simple computation, consisting of a summation of the weighted inputs, followed by the addition of a constant called the threshold or bias, and the application of a nonlinear response (activation) function. The result of the computation of a unit constitutes its output. This output is used as an input for the nodes to which it is linked through an outgoing connection. The overall task of the network is to achieve a certain network configuration, for instance a required input–output relation, by means of the collective computation of the nodes. This process is often called self–organization. Neural Networks algorithms for the TSP are presented in [4,6,53,69].

  • The Ant Colony Optimization (ACO) metaheuristic is a relatively new technique for solving combinatorial optimization problems (COPs). Based strongly on the Ant System (AS) metaheuristic developed by Dorigo, Maniezzo and Colorni [19], ant colony optimization is derived from the foraging behaviour of real ants in nature. The main idea of ACO is to model the problem as the search for a minimum cost path in a graph. Artificial ants walk through this graph, looking for good paths. Each ant has a rather simple behavior so that it will typically only find rather poor-quality paths on its own. Better paths are found as the emergent result of the global cooperation among ants in the colony. An ACO algorithm consists of a number of cycles (iterations) of solution construction. During each iteration a number of ants (which is a parameter) construct complete solutions using heuristic information and the collected experiences of previous groups of ants. These collected experiences are represented by a digital analogue of trail pheromone which is deposited on the constituent elements of a solution. Small quantities are deposited during the construction phase while larger amounts are deposited at the end of each iteration in proportion to solution quality. Pheromone can be deposited on the components and/or the connections used in a solution depending on the problem. Ant Colony Optimization algorithms for the TSP are presented in [16,18,19,70].

  • One way to invest extra computation time is to exploit the fact that many local improvement heuristics have random components, even if in their initial tour construction phase. Thus, if one runs the heuristic multiple times he will get different results and can take the best. The Iterated Lin Kernighan algorithm (ILK) [54] has been proposed by Johnson [39] and it is considered to be one of the best algorithms for obtaining a first local minimum. To improve this local minimum, the algorithm examines other local minimum tours ‘near’ the current local minimum. To generate these tours, ILK first applies a random and unbiased nonsequential 4-opt exchange to the current local minimum and then optimizes this 4-opt neighbor using the LK algorithm. If the tour obtained by this process is better than the current local minimum then ILK makes this tour the current local minimum and continues from there using the same neighbor generation process. Otherwise, the current local minimum remains as it is and further random 4-opt moves are tried. The algorithm stops when a stopping criterion based either on the number of iterations or the computational time is satisfied. Two other approaches are the Iterated 3-opt and the Chained Lin-Kernighan [5], where random kicks are generated from the solution and from these new points the exploration for a better solution is continued [40].

  • Ejection Chain Method provides a wide variety of reference structures, which have the ability to generate moves not available to neighborhood search approaches traditionally applied to TSP [63,64]. Ejection Chains are variable depth methods that generate a sequence of interrelated simple moves to create a more complex compound move. An ejection consists of a succession of operations performed on a given set of elements, where the m t operation changes the state of one or more elements which are said to be ejected in the \( m_t + 1 \) operations. Of course, there is a possibility to appear changes in the state of other elements, which will lead to other ejections, until no more operations can be made [27]. Other Ejection Chain Algorithms are presented in [20,21].

  • Scatter Search is an evolutionary strategy originally proposed by Glover [28,30]. Scatter Search operates on a set of reference solutions to generate a new set of solutions by weighted linear combinations of structured subset of solutions. The reference set is required to be made up of high quality and diverse solutions and the goal is to produce weighted centers of selected subregions that project these centers into regions of the solution space that are to be explored by auxiliary heuristic procedures.

  • Path Relinking [28,30], combines solutions by generating paths between them using local search neighborhoods, and selecting new solutions encountered along these paths.

  • Guided Local Search (GLS), originally proposed by Voudouris and Chang [71,72], is a general optimization technique suitable for a wide range of combinatorial optimization problems. The main focus is on the exploitation of problem and search–related information to effectively guide local search heuristics in the vast search spaces of NP-hard optimization problems. This is achieved by augmenting the objective function of the problem to be minimized with a set of penalty terms which are dynamically manipulated during the search process to steer the heuristic to be guided. GLS augments the cost function of the problem to include a set of penalty terms and passes this, instead of the original one, for minimization by the local search procedure. Local search is confined by the penalty terms and focuses attention on promising regions of the search space. Iterative calls are made to local search. Each time local search gets caught in a local minimum, the penalties are modified and local search is called again to minimize the modification cost function. Guided Local Search algorithms for the TSP are presented in [71,72].

  • Noising Method was proposed by Charon and Hudry [13] and is a metaheuristic where if it is wanted to minimize the function f 1, this method do not take the true values of f 1 into account but it considers that they are perturbed in some way by noises in order to get a noised function f 1 noised. During the run of the algorithm, the range of the perturbing noises decreases (typically to zero), so that, at the end, there is no significant noise and the optimization of f 1 noised leads to the same solution as the one provided by a descent algorithm applied to f 1 with the same initial solution. This algorithm was applied to the Traveling Salesman Problem by Charon and Hudry [14].

  • Particle Swarm Optimization (PSO) is a population‐based swarm intelligence algorithm. It was originally proposed by Kennedy and Eberhart as a simulation of the social behavior of social organisms such as bird flocking and fish schooling [44]. PSO uses the physical movements of the individuals in the swarm and has a flexible and well-balanced mechanism to enhance and adapt to the global and local exploration abilities. PSO algorithms for the solution of the Traveling Salesman Problem are presented in [32,47,73].

  • Variable Neighborhood Search (VNS) is a metaheuristic for solving combinatorial optimization problems whose basic idea is systematic change of neighborhood within a local search [36]. Variable Neighborhood Search algorithms for the TSP are presented in [52].