This paper introduces a new path relinking algorithm for the well-known quadratic assignment problem (QAP) in combinatorial optimization. The QAP has attracted considerable attention in research because of its complexity and its applicability to many domains. The algorithm presented in this study employs path relinking as a solution combination method incorporating a multistart tabu search algorithm as an improvement method. The resulting algorithm has interesting similarities and contrasts with particle swarm optimization methods. Computational testing indicates that this algorithm produces results that rival the best QAP algorithms. The authors additionally conduct an analysis disclosing how different strategies prove more or less effective depending on the landscapes of the problems to which they are applied. This analysis lays a foundation for developing more effective future QAP algorithms, both for methods based on path relinking and tabu search, and for hybrids of such methods with related processes found in particle swarm optimization.
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
P is the set of all
n-vector permutations. For each pair of assignments
and
in
p the flow
between the two facilities
i and
j is multiplied by the distance
between the two locations
r and
s. 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).
In this study we develop a new path relinking algorithm for the QAP that combines a number of adaptive memory strategies that have shown promise in previous studies. We demonstrate highly satisfactory results for two of the more difficult well-known test sets for the QAP. In addition, competitive results are obtained against some of the best metaheuristics for the QAP.