Article Preview
Top1. Introduction
The quadratic assignment problem (QAP) is a classical NP-hard combinatorial optimization problem that has been extensively studied. In the context of facility location, the objective is to find a minimum cost assignment of facilities to locations considering the flow of materials between facilities and the distance between locations. The problem may be formulated as follows:
(1) where
f is the flow matrix,
d is the distance matrix,
p is a permutation vector of
n indexes of facilities (or locations) mapping a possible assignment of
n facilities to
n locations, and
is the set of all
n-vector permutations. For each pair of assignments
and
in
p the flow
between the two facilities
and
is multiplied by the distance
between the two locations
and
The sum of these terms over all pairs gives the total cost assignment
for the permutation
p. The objective is to find a permutation
in
of minimum total cost.
In addition to the facility location context, the QAP is useful in a variety of other domains, including electronics, chemistry, manufacturing, computation, data analysis, and transportation. See for example, Cela (1998) for a comprehensive discussion of these applications.
Metaheuristic approaches have been popularly applied to the QAP due to the limitations of exact methods to solve such problems within the computational boundaries of existing technology. Metaheuristic solution techniques applied to the QAP have included tabu search (Taillard, 1991; Misevicius, 2005; James, Rego, & Glover, 2009), scatter search (Cung et al., 1996), genetic algorithms (Fleurent & Ferland, 1994; Ahuja, Orlin, & Tiwari, 2000; Misevicius, 2003, 2004; Drezner, 2003, 2005), GRASP (Li, Pardalos, & Resende, 1994), path-relinking (James, Rego, & Glover, 2005), hybrid approaches of GRASP with path relinking (Oliveira, Pardalos, & Resende, 2004), iterative local search (Hussin & Stützle, 2009; Ramkumar, Ponnambalam, & Jawahar, 2009; Stützle, 2006), and several forms of particle swarm optimization (Stützle & Dorigo, 1999; Iordache, 2010).