VNS-RAC: A hybrid Variable Neighborhood Search and Ant Colony Optimization Algorithm with Ranking for the Quadratic Assignment Problem.

摘要

This research seeks to test the effectiveness of a proposed hybrid Variable Neighborhood Search (VNS) / Ant Colony Optimization (ACO) algorithm on a wide range of Quadratic Assignment Problem (QAP) instances. Known as Variable Neighborhood Search - Ranked Ant Colonies (VNS-RAC), the key feature of the proposed algorithm is its application of colony-based and ranking methods to the Variable Neighborhood Search - Ant (VNS-ANT) algorithm, a previous, colony-less approach. Various QAP instances were chosen for benchmarking VNS-RAC. Results have shown that on the basis of solution quality, the two variants of the proposed algorithm tested are superior to the baseline (based on the existing VNS-ANT algorithm) in nearly all cases. Additionally, on the basis of the average number of convergence iterations, improvements were discovered in most cases. This is very promising, as it means that the VNS-RAC algorithm could be one of the best ACO algorithms available for the QAP.