Article ID: | iaor200924644 |
Country: | United States |
Volume: | 18 |
Issue: | 4 |
Start Page Number: | 433 |
End Page Number: | 443 |
Publication Date: | Oct 2006 |
Journal: | INFORMS Journal On Computing |
Authors: | Laporte Gilbert, Gaudioso Manlio, Moccia Luigi, Cordeau JeanFranois |
Keywords: | heuristics |
In the generalized quadratic assignment problem (GQAP) we are given n weighted facilities, m capacitated sites, a traffic intensity matrix between facilities, a distance matrix between sites, unit traffic costs, and assignment costs of facilities to sites. The aim is to determine an assignment of facilities to sites so that the sum of assignment and traffic costs is minimized and the total weight of all facilities assigned to the same site does not exceed the site capacity. The GQAP is a generalization of the quadratic assignment problem (QAP) in which n = m and exactly one facility must be assigned to each site. The problem has applications in container yard management and in the assignment of equipment to manufacturing sites. This article describes a memetic heuristic for the GQAP, as well as an integer linear programming formulation that can be solved by CPLEX for small instances. For larger instances, feasible solutions can be obtained by a truncated branch–and–bound procedure. Computational experiments show that on small instances the proposed heuristic always yields an optimal solution; on larger instances it always outperforms the truncated branch–and–bound algorithm.