A tabu search heuristic for a generalized quadratic assignment problem

Abstract

The generalized quadratic assignment problem (GQAP) is the task of assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may have different space requirements, and the locations may have varying space capacities. Also, multiple facilities may be assigned to each location such that space capacity is not exceeded. In this paper, an application of the GQAP is presented for assigning a set of machines to a set of locations on the plant floor. Construction algorithms and a simple tabu search heuristic are developed for the GQAP. A set of test problems available in the literature was used to evaluate the performances of the TS heuristic using different construction algorithms. The results show that the simple TS heuristic is effective for solving the GQAP.

Keywords:

• Generalized quadratic assignment problem
• tabu search
• metaheuristic
• construction algorithms