Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons

Journal of Industrial Engineering International

دوره 8، شماره 1، فروردین 2012   

نویسندگان

Mahdi Bashiri^{* 1}؛ Hossein Karimi²

¹Department of Industrial Engineering, Shahed University, Tehran 3319118651, Iran

²Department of Industrial Engineering, Shahed University, Tehran, 3319118651, Iran

چکیده

Quadratic assignment problem (QAP) is a well-known problem in the facility location and layout. It belongs to the
NP-complete class. There are many heuristic and meta-heuristic methods, which are presented for QAP in the
literature. In this paper, we applied 2-opt, greedy 2-opt, 3-opt, greedy 3-opt, and VNZ as heuristic methods and
tabu search (TS), simulated annealing, and particle swarm optimization as meta-heuristic methods for the QAP. This
research is dedicated to compare the relative percentage deviation of these solution qualities from the best known
solution which is introduced in QAPLIB. Furthermore, a tuning method is applied for meta-heuristic parameters.
Results indicate that TS is the best in 31% of QAPs, and the IFLS method, which is in the literature, is the best in 58
% of QAPs; these two methods are the same in 11% of test problems. Also, TS has a better computational time
among heuristic and meta-heuristic methods.

کلیدواژه‌ها

Quadratic assignment problem؛ Heuristics؛ Meta-heuristics؛ Tuning method