Effect of Neighborhood Generation on Simulated Annealing Optimization Algorithm for Traveling Salesman problem

The Traveling Salesman Problem (TSP) is one of the most studied non-deterministic polynomial problems that has been used in various sectors of science and technology. Several types of optimization techniques and algorithms have been developed to solve this problem competently. Among those algorithms, an evolutionary and easily implementable technique such as the Simulated Annealing (SA) Algorithm has been used the most to solve this complex problem. It was first independently presented as a search algorithm for combinatorial optimization problems. In this work, we present a heuristic-based SA algorithm in order to analyze the effects of neighborhood search operators on the solution quality of this algorithm for solving TSP. In fact, three different neighborhood search operators such as swap, insertion, and reversion are applied to the SA algorithm to generate better solutions. A set of better routes are improved through the iterative process of the algorithm. The experiments are conducted on a collection of symmetric TSP datasets taken from TSPLIB to evaluate the algorithm. The experimental results show that the operator insertion provides a better solution than the other operators, while the swap consumes less computational time.

• Supervision