A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem

The generalized quadratic assignment problem (GQAP) involves assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. Unlike the traditional one-to-one assignment problem, the GQAP is a many-to-one assignment problem. That is, multiple facilities can be assigned to each location without exceeding the capacity of the location. This research was motivated by the problem of assigning multiple facilities (e.g., machines or equipment) to locations at manufacturing plants. Another well-known application of the GQAP includes the assignment of facilities (i.e., containers) to locations (i.e., storage areas) in container yards. This paper presents simple but very effective approximation algorithms for solving real-world, large-size GQAP instances quickly without spending a lot of time setting the algorithm parameters, since there are few parameters to set. More specifically, a construction algorithm is used to generate an initial solution for the proposed problem, and the initial solution is improved using a simulated annealing algorithm. The performance of the proposed algorithms is tested with respect to solution quality and computation time on a set of test problems available in the literature. The results show the effectiveness of the proposed algorithms.