Solution Methods for the Dynamic Generalized Quadratic Assignment Problem

In this paper, the generalized quadratic assignment problem (GQAP) is extended to consider multiple time periods and is called the dynamic GQAP (DGQAP). This problem considers assigning a set of facilities to a set of locations for multiple periods in the planning horizon such that the sum of the transportation, assignment, and reassignment costs is minimized. The facilities may have different space requirements (i.e., unequal areas), and the capacities of the locations may vary during a multi-period planning horizon. Also, multiple facilities may be assigned to each location during each period without violating the capacities of the locations. This research was motivated by the problem of assigning multiple facilities (e.g., equipment) to locations during outages at electric power plants. This paper presents mathematical models, construction algorithms, and two simulated annealing (SA) heuristics for solving the DGQAP problem. The first SA heuristic (SAI) is a direct adaptation of SA to the DGQAP, and the second SA heuristic (SAII) is the same as SAI with a look-ahead/look-back search strategy. In computational experiments, the proposed heuristics are first compared to an exact method on a generated data set of smaller instances (data set 1). Then the proposed heuristics are compared on a generated data set of larger instances (data set 2). For data set 1, the proposed heuristics outperformed a commercial solver (CPLEX) in terms of solution quality and computational time. SAI obtained the best solutions for all the instances, while SAII obtained the best solution for all but one instance. However, for data set 2, SAII obtained the best solution for nineteen of the twenty-four instances, while SAI obtained five of the best solutions. The results highlight the effectiveness and efficiency of the proposed heuristics, particularly SAII, for solving the DGQAP.