Variable Block Insertion Heuristic for the Quadratic Assignment Problem

Abstract

The aim of this paper is to apply the variable block insertion heuristic (VBIH) algorithm recently proposed in the literature for solving the quadratic assignment problem (QAP). The VBIH algorithm is concerned with making block moves in a given solution. As a local search in this paper the VNST is employed from the literature to be applied to a solution obtained after several block moves. Besides the single-solution based VBIH we also propose a populated VBIH (PVBIH) in this paper. The proposed algorithms were evaluated on quadratic assignment problem instances arising from real life problems as well as on a number of benchmark instances from the QAPLIB. The computational results show that the proposed algorithms are very effective in solving both types of instances. All PCB instances are further improved.