Summary
the 2014 International Symposium on Nonlinear Theory and its Applications
2014
Session Number:B1L-C
Session:
Number:B1L-C2
Performance analysis of adaptive tabu search for quadratic assignment problems
Akio Watanabe, Yutaka Shimada, Kantaro Fujiwara, Takaomi Shigehara, Tohru Ikeguchi,
pp.241-244
Publication Date:2014/9/14
Online ISSN:2188-5079
DOI:10.34385/proc.46.B1L-C2
PDF download (73.6KB)
Summary:
The quadratic assignment problem is one of the NP-hard combinatorial optimization problems. In this paper, we analyzed solvable performance of an adaptive local search algorithm for solving quadratic assignment problems which has similar searching characteristic to the Lin- Kernighan algorithm for solving traveling salesman problems. We also analyzed the proposed adaptive local search algorithm with tabu search dynamics. Using results obtained from the analysis, we proposed a new adaptive local search algorithm with less variable depth. Evaluating the performances of the proposed algorithms, we found that the new adaptive local search algorithm has high performance with less calculation costs by modified for tabu search.