Path Relinking with Multi-Start Tabu Search for the Quadratic Assignment Problem

Path Relinking with Multi-Start Tabu Search for the Quadratic Assignment Problem

Tabitha James (Virginia Tech, USA) and Cesar Rego (University of Mississippi, USA)
Copyright: © 2011 |Pages: 19
DOI: 10.4018/jsir.2011040104
OnDemand PDF Download:
No Current Special Offers


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.
Article Preview

1. 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 jsir.2011040104.m02 is the set of all n-vector permutations. For each pair of assignments jsir.2011040104.m03 and jsir.2011040104.m04 in p the flowjsir.2011040104.m05between the two facilities jsir.2011040104.m06 and jsir.2011040104.m07is multiplied by the distance jsir.2011040104.m08 between the two locations jsir.2011040104.m09and jsir.2011040104.m10 The sum of these terms over all pairs gives the total cost assignment jsir.2011040104.m11 for the permutation p. The objective is to find a permutation jsir.2011040104.m12 in jsir.2011040104.m13 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).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 12: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing