Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP) consists of assigning n facilities to n locations so as 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 size instances (typically, n is less than or equal to 25). Neighborhood search algorithms are the most popular heuristic algorithms to solve larger size instances of the QAP. The most extensively used neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities and thus has size O(n^2). Previous efforts to explore larger size 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 where the size of the neighborhood is very large and we propose a novel search procedure to heuristically enumerate good neighbors. Our search procedure relies on the concept of improvement graph which allows us to evaluate neighbors much faster than the existing methods. We present extensive computational results of our algorithms on standard benchmark instances. These investigations reveal that very large-scale neighborhood search algorithms give consistently better solutions compared the popular 2-exchange neighborhood algorithms considering both the solution time and solution accuracy
Year of publication: |
2002
|
---|---|
Authors: | Ahuja, Ravindra K. ; Jha, Krishna ; Orlin, James B. ; Sharma, Dushyant |
Publisher: |
[S.l.] : SSRN |
Saved in:
freely available
Extent: | 1 Online-Ressource (28 p) |
---|---|
Type of publication: | Book / Working Paper |
Language: | English |
Notes: | Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments July 2002 erstellt |
Other identifiers: | 10.2139/ssrn.337600 [DOI] |
Source: | ECONIS - Online Catalogue of the ZBW |
Persistent link: https://www.econbiz.de/10014106635
Saved in favorites
Similar items by person
-
Exact and Heuristic Methods for the Weapon Target Assignment Problem
Ahuja, Ravindra K., (2006)
-
Exact and Heuristic Methods for the Weapon Target Assignment Problem
Ahuja, Ravindra K., (2004)
-
Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem
Ahuja, Ravindra K., (2007)
- More ...