# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 1 Introduction  
Assignment problems have a wide range of real-world applications in different fields ranging from logistics, manufacturing, business, telecommunications, healthcare, etc., There are mainly two types of assignment problems: one-to-one and many-to-one. For example, consider the problem of assigning facilities to locations, while minimizing the sum of the assignment costs, such that each facility is assigned to a location, and each location is assigned to a facility. This problem is called a one-to-one assignment problem. In contrast, in a many-to-one assignment problem, multiple facilities may be assigned to each location without exceeding the capacities of the locations. This problem is called the generalized assignment problem. For real-life applications of the generalized assignment problem (GAP) in scheduling, timetabling, telecommunication, facility location, transportation, production planning, etc., see [PERSON] [1]. This research was motivated by the challenge of efficiently assigning facilities (e.g., equipment, machines) to locations within a manufacturing plant. Besides assigning multiple facilities to each location without exceeding the capacities of the locations, the objective was to minimize the sum of the assignment and transportation costs. The assignment costs consist of the cost of assigning or installing each machine to a location, and the transportation costs consist of the costs of moving materials processed on the machines between the machines. Since the transportation cost introduces a quadratic term in the objective function, as will be discussed below, this problem is called the generalized quadratic assignment problem (GQAP). The GQAP was first introduced by [PERSON] and [PERSON] [2]. The authors considered the problem of assigning equipment to locations at different manufacturing sites. They presented a nonlinear mathematical model, three linearization methods, and a branch-and-bound algorithm to optimally solve the problem. [PERSON] and [PERSON] [3] presented the first implementation of the GQAP to design the curriculum at a university. The authors presented a model for their problem. They linearized and solved their model using an exact algorithm within a solver. [PERSON] [4] applied an exact algorithm, which uses a reformulation linearization technique, to solve the cross-dock door assignment problem which is a special case of the GQAP. Other exact algorithms for solving the GQAP were presented by [PERSON] et al. [5], [PERSON] et al. [6], and [PERSON] et al. [7]. Since the GQAP is a generalization of the QAP, which is NP-hard ([PERSON] and [PERSON] [8]), the GQAP is NP-hard. Therefore, only small- to medium-size GQAP instances can be solved in reasonable computational time. Thus, approximation algorithms were designed for solving large-sized GQAP instances. [PERSON] et al. [9] considered the GQAP application where containers were assigned to storage locations in a container yard. The authors presented a linearized model and a memetic algorithm (MA) which combined a genetic algorithm with tabu search (TS). [PERSON] et al. [10] designed a global harmony search algorithm to solve the task assignment problem, which is a type of GQAP used to assign tasks to processors. [PERSON] et al. [11] proposed several greedy randomized adaptive search procedures (GRASPs) with path-relinking heuristic algorithms for the GQAP. [PERSON] and [PERSON] [12] presented several construction algorithms and a TS algorithm for the GQAP which considered assigning machines and equipment to locations in manufacturing plants. [PERSON] [13] presented a TS and a simulated annealing (SA) algorithm for the GQAP. However, the SA algorithm was unable to obtain several of the best-known solutions on a set of test problems available in the literature with long average run times. [PERSON] et al. [14] designed a parallel memetic iterated TS heuristic algorithm for the quadratic assignment problem and four of its variants, which included the GQAP.