Presentation | 2010-03-09 Soft Tabu Search for Solving Traveling Salesman Problem Takafumi MATSUURA, Tohru IKEGUCHI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Traveling Salesman Problem / tabu search / soft tabu search / 2-opt algorithm / meta-heuristics |
Paper # | NLP2009-163 |
Date of Issue |
Conference Information | |
Committee | NLP |
---|---|
Conference Date | 2010/3/2(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Nonlinear Problems (NLP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Soft Tabu Search for Solving Traveling Salesman Problem |
Sub Title (in English) | |
Keyword(1) | Traveling Salesman Problem |
Keyword(2) | tabu search |
Keyword(3) | soft tabu search |
Keyword(4) | 2-opt algorithm |
Keyword(5) | meta-heuristics |
1st Author's Name | Takafumi MATSUURA |
1st Author's Affiliation | Graduate School of Science and Engineering, Saitama University() |
2nd Author's Name | Tohru IKEGUCHI |
2nd Author's Affiliation | Saitama Uneversity Brain Science Institute |
Date | 2010-03-09 |
Paper # | NLP2009-163 |
Volume (vol) | vol.109 |
Number (no) | 458 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |