This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ahuja, R. K. Articles by Sharma, D. Search for Related Content

Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem

Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Innovative Scheduling, Inc., Gainesville Technology Enterprise Center, Gainesville, Florida 32641
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
ahuja{at}ufl.edu
krishna{at}innovativescheduling.com
jorlin{at}mit.edu
dushyant{at}umich.edu

The quadratic assignment problem (QAP) consists of assigning n facilities to n locations to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse settings, is known to be NP-hard, and can be solved to optimality only for fairly small instances (typically, n 30). Neighborhood search algorithms are the most popular heuristic algorithms for solving larger instances of the QAP. The most extensively applied neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities; its size is therefore O(n²). Previous efforts to explore larger neighborhoods (such as 3-exchange or 4-exchange neighborhoods) were not very successful, as it took too long to evaluate the larger set of neighbors. In this paper, we propose very large-scale neighborhood (VLSN) search algorithms when the size of the neighborhood is very large, and we propose a novel search procedure to enumerate good neighbors heuristically. Our search procedure relies on the concept of an improvement graph that allows us to evaluate neighbors much faster than existing methods. In this paper, we present extensive computational results of our algorithms when applied to standard benchmark instances.

Key words: neighborhood search; heuristics; combinatorial optimization; quadratic assignment problem; computational testing
History: received July 2002; revised March 2005; accepted June 2006.