A scatter search based approach for the quadratic assignment problem

Scatter search is an evolutionary heuristic, proposed two decades ago, that uses linear combinations of a population subset to create new solutions. A special operator is used to ensure their feasibility and to improve their quality. In this paper, we propose a scatter search approach to the QAP problem. The basic method is extended with intensification and diversification stages and we present a procedure to generate good scattered initial solutions.