An analytical comparison to heuristic and meta- heuristic solution methods for Quadratic Assignment Problem

Quadratic Assignment Problem (QAP) is a well known problem in the facility location and layout. It belongs to NP-Complete class, so that the exact solution methods consume much computational time. There are some heuristic and meta-heuristic methods presented for this problem in the literature. In this paper we applied 3-Opt, greedy 3-Opt, 3-Opt, greedy 3-Opt and VNZ as the heuristic methods and TS (Tabu Search), SA (Simulated Annealing) and PSO (Particle Swarm Optimization) as the meta-heuristic methods for the QAP. This research dedicated to compare their gap with optimum solution for the selected data set from the QAPLIB. Results show that 3-Opt as a heuristic method and TS which belongs to meta-heuristic methods have a better solution in less computational time. Finally some more analysis has been illustrated in the paper.

Quadratic Assignment Problem, Heuristics, Metaheuristics, Analysis