Comparison of iterative searches for the quadratic assignment problem

This paper compares some of the most efficient heuristic methods for the quadratic assignment problem. These methods are known as strict taboo search, robust taboo search, reactive taboo search and genetic hybrids. It is shown that the efficiency of these methods strongly depends on the problem type and that no one method is better than all the others. A fast method for tuning the short term memory parameters of taboo searches is proposed and its validity is experimentally verified on long searches. A new type of quadratic assignment problem occurring in the design of grey patterns is proposed and it is shown how to adapt and improve the existing iterative searches for this specific problem. Finally, the usual way of implementing approximations of strict taboo search is discussed and better approximations are proposed