TY - JOUR
T1 - A comprehensive review of quadratic assignment problem
T2 - variants, hybrids and applications
AU - Abdel-Basset, Mohamed
AU - Manogaran, Gunasekaran
AU - Rashad, Heba
AU - Zaied, Abdel Nasser H.
N1 - Publisher Copyright:
© 2018 Springer-Verlag GmbH Germany, part of Springer Nature
PY - 2018/6/20
Y1 - 2018/6/20
N2 - The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.
AB - The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.
KW - Complexity
KW - Exact approaches
KW - Formulations
KW - Heuristics approaches
KW - Metaheuristic approaches
KW - NP-hard
KW - Quadratic assignment problem
UR - http://www.scopus.com/inward/record.url?scp=85049559984&partnerID=8YFLogxK
U2 - 10.1007/s12652-018-0917-x
DO - 10.1007/s12652-018-0917-x
M3 - Article
AN - SCOPUS:85049559984
SN - 1868-5137
VL - 9
SP - 1
EP - 24
JO - Journal of Ambient Intelligence and Humanized Computing
JF - Journal of Ambient Intelligence and Humanized Computing
IS - 3
ER -