GRASP with path-relinking for the generalized quadratic assignment problem

G.R. Mateus (mateusdcc.ufmg.br)
M.G.C. Resende (mgcrresearch.att.com)
R.M.A. Silva (rmasdcc.ufla.br)

Abstract: The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.

Keywords: Generalized quadratic assignment problem, heuristic, GRASP, path-relinking, experimental algorithm.

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report TD-7MZQ5R, AT&T Labs Research, Florham Park, NJ 07932, January 5, 2009. Revised November 25, 2009.

Download: [PDF]

Entry Submitted: 01/05/2009
Entry Accepted: 01/08/2009
Entry Last Modified: 11/25/2009

Modify/Update this entry