Journal
JOURNAL OF HEURISTICS
Volume 17, Issue 5, Pages 527-565Publisher
SPRINGER
DOI: 10.1007/s10732-010-9144-0
Keywords
Generalized quadratic assignment problem; Heuristic; GRASP; Path-relinking; Experimental algorithm
Funding
- Brazilian National Council for Scientific and Technological Development (CNPq)
- Foundation for Support of Research of the State of Minas Gerais, Brazil (FAPEMIG)
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available