Hybrid simulated annealing for the bi-objective quadratic assignment problem

Past research has shown that the performance of algorithms for solving the Quadratic Assignment Problem (QAP) depends on the structure and the size of the instances. In this paper, we study the bi-objective QAP, which is a multi-objective extension of the single-objective QAP to two objectives. The algorithm we propose extends a high-performing Simulated Annealing (SA) algorithm for large-sized, single-objective QAP instances to the bi-objective context. The resulting Hybrid Simulated Annealing (HSA) algorithm is shown to clearly outperform a basic, hybrid iterative improvement algorithm. Experimental results show that HSA clearly outperforms basic Hybrid Iterative Improvement. When compared to state-of-the-art algorithms for the bQAP, a Multi-objective Ant Colony Optimization algorithm and the Strength Pareto Evolutionary Algorithm 2, HSA shows very good performance, outperforms the former in most cases, and showing competitive performance to the latter.SCOPUS: cp.k