A VNS-ANT Algorithm to QAP

Quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems which has been tackled by many metaheuristic algorithms. This paper proposes a new algorithm, VNS-ANT, to solve QAP. The main idea is to hybridize a VNS (variable neighborhood search) mechanism and an ant algorithm (FANT). VNS-ANT enhances the local search in ANT with a VNS search in k-distance space guided by ant pheromone. In this way, VNS-ANT algorithm can not only efficiently speedup the improvement procedure in ANT, but sufficiently improve the veracity of VNS. The paper tests VNS-ANT on famous instances of QAPLIB. The experimental results show that VNS-ANT obtains better solutions than FANT with average 14.4% higher in solution quality.