# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 1 Introduction
Besides presenting an exact algorithm (i.e., Benders reformulation) for the GQAP, [PERSON] et al. [7] proposed an adaptive large neighborhood search algorithm. [PERSON] et al. [15] designed a TS metaheuristic for the GQAP. The authors mentioned that the GQAP has been used to model several applications such as order picking, storage layout in warehouse management, relational database design, and scheduling activities in semiconductor wafer processing. As can be seen by this literature review, there are many diverse applications of the GQAP as it relates to real-world problems. SA is a stochastic metaheuristic algorithm that uses the idea of the annealing process of solids to solve combinatorial optimization problems (COPs). [PERSON] et al. [16] were the first to use SA to solve COPs. [PERSON] et al. [17] presented two SA heuristics to solve a dynamic QAP, called the dynamic facility layout problem. More recently, [PERSON] et al. [18] presented an SA heuristic for a task assignment and path planning problem which is viewed as a three-dimensional vehicle routing problem. This problem is a generalization of the generalized assignment problem combined with multiple traveling salesperson problems. [PERSON] et al. [19] developed an SA heuristic for a home health care location-routing problem with a mixed fleet of electric and conventional vehicles that considers battery swapping stations. [PERSON] et al. [20] used an SA heuristic to solve a new variant of the bin-packing problem called the circular bin-packing problem with rectangular items. In addition, [PERSON] et al. [21] developed an SA algorithm to schedule trucks and allocate truckloads to compatible trucks for transporting logs. As illustrated above, the SA algorithm has been successfully used to solve many different types of COPs. For more details on SA, see [PERSON] and [PERSON] [22], [PERSON] [23], or [PERSON] et al. [24]. In this paper, the GQAP is considered which involves assigning a set of facilities (e.g., machines or equipment) to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may be of different sizes, and the locations may have varying space capacities. In addition, multiple facilities may be assigned to each location whereas location capacities are not exceeded. The objective of this research is to present 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. As a result, a construction algorithm and an SA algorithm is presented for the proposed problem, since there are fewer parameters to set in the SA algorithm, compared to most of the other algorithms available in the GQAP literature. Furthermore, some other advantages of SA are as follows:  
1. SA, a single solution algorithm, can find \"good\" solutions quickly compared to population-based algorithms for certain COPs ([PERSON] et al. [24]). As indicated in [PERSON] et al. [9] and in [PERSON] et al. [14], constructing/finding a population of solutions, especially for tightly constrained GQAP instances, can be computationally costly. 2. SA can easily handle problems with complex objective functions and constraints ([PERSON] [23] and [PERSON] et al. [24]). 3. SA is easier to implement quickly since it is easier to understand and code compared to many other algorithms ([PERSON] and [PERSON] [22], [PERSON] [23], and [PERSON] et al. [24]). In this paper, mathematical models, a construction algorithm, and an SA algorithm are presented for the GQAP. In Section 2, the mathematical models are presented for the GQAP, and an illustrative example is solved using one of the proposed models. The construction algorithm and an SA algorithm for the GQAP is presented in Section 3. In Section 4, some computational results of the proposed solution methods, on a set of test problems taken from the literature, are given. Finally, Section 5 provides conclusions.