Tabu Search (TS) is a robust neighborhood search algorithm used to solve a wide range of combinatorial optimization problems. In this paper, the effects of six neighborhood generation and move selection mechanisms on the performance of TS are investigated. Among these strategies is a newly proposed dynamic neighborhood which is shown to be efficient in solving the problem under consideration. To compare the performance of these strategies, a set of constrained Traveling Salesman Problems (TSP) is solved using different neighborhoods. Computational results are then compared in terms of solution qualities and convergence speeds. The results show that Tabu Search performance is greatly affected by the neighborhood generation mechanism and move selection policy.

Keywords