A Survey of Meta-Heuristic Solution Methods for the Quadratic Assignment Problem
Hassan Mishmast Nehi, Shahin Gelareh · 2007
The quadratic assignment problem (QAP) belongs to the class of NP-Hard problems and also is one of the hardest problems in this class. Today, regarding current hardware, solving the large size instances of this problem, using exact methods, is not possible in reasonable amount of time. In this way many heuristic (Meta-heuristic) and approximation methods and soft-computing approaches have been applied to this problems that we will review some of them in this paper. The aim of this paper is to compare some of efficient heuristic (Meta-heuristic) and soft-computing methods known up to now. Some of them are imitated from the nature’s behavior while some other are most analytical. These methods are known as Ant Colony Optimization (ACO), Artificial Neural Networks (NN), Genetic Algorithms (GA), Scatter Search (SS), Simulated Annealing (SA), Tabu Search (TS) and Greedy Randomized Adaptive Search Procedure (GRASP).