Quadratic Assignment Problem (Model, Applications, Solutions): Review Paper

Abstract

In operations research, Quadratic Assignment Problem (QAP) is a significant combinatorial optimization problem. When the size of the QAP problem increases, it becomes impossible to solve the problem in polynomial time. Several practical problems such as hospital and campus layout, allocation of gates to airplanes in airports and electrical backboard wiring problems can be modeled as QAP. The QAP model seeks to identify the optimal distribution of N facilities to N locations  in a way that minimizes the total traveling cost based on the distance between every pair of a location and the amount of traffic between every pair of facilities of organizational units within a building. Against this background, there are two main approaches have been suggested to deal with  QAP, and they are, the Exact and Approximate (Heuristic and Metaheuristic) approaches. The exact approach provides a global optimal solution for the small size of QAP, while the approximate approaches can find the optimal or a near-optimal solution at a reasonable time for large-sized QAP. The objectives of this study are as follows: (i) To analysis the QAP model, (ii) To conduct a comprehensive survey of the methods that have been used to solve the QAP model, (iii)  To identify the issues and limitations of the methods in (ii), and (iv) to explore the best approach that can be used in enhancing the solutions of QAP model within a reasonable time based on the accuracy of algorithm. The results show that the hybrid metaheuristic approach has the capability of finding the best results within a reasonable time for the large sized problem.