A Dynamic Scatter Search Algorithm for Solving Traveling Salesman Problem

Abstract

Scatter Search (SS) is a population-based evolutionary metaheuristic algorithm that selects solutions from a specific memory called a reference set (RefSet) to produce other diverse solutions. In this work, a dynamic SS algorithm is proposed to solve the symmetric traveling salesman problem (TSP). To improve the performance of SS, a dynamic RefSet update and a dynamic population update are proposed. To test the performance of the proposed algorithm, computational experiments are carried out on the basis of the benchmark instances of the problem. The computational results show that the performance of the proposed algorithm is effective in solving the TSP