A FLEXIBLE, POLYNOMIAL-TIME, CONSTRUCTION AND IMPROVEMENT HEURISTIC FOR THE QUADRATIC ASSIGNMENT PROBLEM

This paper 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. 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 with 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 in the literature is provided to evaluate the worth of this method.