A flexible construction and improvement heuristic for the quadratic assignment problem

This thesis is concerned with the development of heuristic algorithms for the popular Quadratic Assignment Problem (QAP) which finds a wide variety of applications in various fields. This discrete optimization problem, which seeks the placement of m facilities on m locations in order to minimize a quadratic interactive cost, is well known to be NP-hard and turns out to be computationally intractable for even moderately sized problems. Hence, problems involving more than 12-15 facilities usually need to be analysed by approximate solution procedures.

The more successful heuristic procedures which exist for problem QAP are computationally intensive, some of these resulting from a premature termination of exact solution procedures. The motivation here is to develop a polynomial time heuristic which is effective with respect to the quality of solutions obtained, while at the same time not being computationally very expensive.

The method proposed herein is flexible in that one can operate it to suitably trade solution quality against effort as desired, and is portable in that the modules used as building blocks can be employed in conjunction with other heuristics as well. Computational experience on test problems found in the literature is provided to evaluate the worth of this method.