Wee Loon Lim

The quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem with a wide variety of applications. Biogeography-based optimization (BBO), a relatively new optimization technique based on the biogeography concept, uses the idea of migration strategy of species to derive algorithm for solving optimization problems. It has been shown that BBO provides performance on a par with other optimization methods. A classical BBO algorithm employs the mutation operator as its diversification strategy. However, this process will often ruin the quality of solutions in QAP. In this paper, we propose a hybrid technique to overcome the weakness of classical BBO algorithm to solve QAP, by replacing the mutation operator with a tabu search procedure. Our experiments using the benchmark instances from QAPLIB show that the proposed hybrid method is able to find good solutions for them within reasonable computational times. Out of 61 benchmark instances tested, the proposed method is able to obtain the best known solutions for 57 of them.

The generalized quadratic assignment problem (GQAP) concerns with assigning m facilities to n locations. Multiple facilities can be assigned to a single location as long as the space allows. The aim is to find a way of assignment such that the total cost involved is minimized while respecting the space constraints. The total cost composes of installation and transportation costs, which is obtained by multiplying the facility flows and distances. GQAP is the generalization of the well-known quadratic assignment problem, which requires the number of facilities and locations to be the same and exactly one facility is assigned to one location. This paper presents a hybrid metaheuristic for solving the GQAP. The proposed algorithm hybridizes biogeography-based optimization with tabu search. Experimental results show that the hybrid metaheuristic is able to solve problem instances obtained from a manufacturing company, within reasonable computational times.