Soft Tabu Search for Solving Traveling Salesman Problem

摘要

To avoid local minima of combinatorial optimization problems, the tabu search have been proposed. Although the tabu search is one of the powerful meta-heuristic methods for the traveling salesman problem and the quadratic assignment problem, the tabu search is not effective for the motif extraction problem because the tabu effect of the tabu search is too strong. Then, we have already proposed a soft tabu search to resolve this problem. Most different point between the soft tabu search and the tabu search is that the tabu effect in the tabu search prohibits to select the same solutions for a while, while in the soft tabu search, the same solutions are hard to be selected for a while. Due to such weak tabu effect, the soft tabu search shows good performances for the motif extraction problem. In this report, to investigate searching ability of the soft tabu search, we apply the soft tabu search to the traveling salesman problem. As a result, the soft tabu search shows also higher performance than the tabu search for the traveling salesman problem.