IRMA-International.org: Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

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

Path Relinking with Multi-Start Tabu Search for the Quadratic Assignment Problem
View Sample PDF
Author(s): Tabitha James (Virginia Tech, USA) and Cesar Rego (University of Mississippi, USA)
Copyright: 2013
Pages: 19
Source title: Recent Algorithms and Applications in Swarm Intelligence Research
Source Author(s)/Editor(s): Yuhui Shi (Southern University of Science and Technology (SUSTech), China)
DOI: 10.4018/978-1-4666-2479-5.ch004

Purchase

View Path Relinking with Multi-Start Tabu Search for the Quadratic Assignment Problem on the publisher's website for pricing and purchasing information.

Abstract

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.

Related Content

Rafael Martí, Juan-José Pantrigo, Abraham Duarte, Vicente Campos, Fred Glover. © 2013. 21 pages.
Peng-Yeng Yin, Fred Glover, Manuel Laguna, Jia-Xian Zhu. © 2013. 20 pages.
Volodymyr P. Shylo, Oleg V. Shylo. © 2013. 10 pages.
Tabitha James, Cesar Rego. © 2013. 19 pages.
Gary G. Yen, Wen-Fung Leong. © 2013. 25 pages.
Shi Cheng, Yuhui Shi, Quande Qin. © 2013. 29 pages.
Xin-She Yang. © 2013. 12 pages.
Body Bottom