A memetic heuristic for the generalized quadratic assignment problem

A memetic heuristic for the generalized quadratic assignment problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.