Breakout local search for the quadratic assignment problem
Breakout local search for the quadratic assignment problem
复制标题
DOI：
10.1016/j.amc.2012.10.106
复制
发表时间：
2013-01-01
影响因子：
4
通讯作者：
Hao, Jin-Kao
中科院分区：
文献类型：
--
作者：
Benlic, Una;Hao, Jin-Kao
二次分配问题是一类研究最多的组合优化问题，具有广泛的实际应用。在本文中，我们提出了突破局部搜索（BLS）解决QAP。BLS通过联合使用局部搜索和自适应扰动策略来探索搜索空间。QAPLIB基准实例集的实验结果表明，该方法是能够达到目前最知名的结果，但两个实例的平均计算时间小于4.5小时。还提供了比较，以显示所提出的方法相对于从文献中的最佳性能的QAP算法的竞争力。(C)2012 Elsevier Inc. All rights reserved.
The quadratic assignment problem (QAP) is one of the most studied combinatorial optimization problems with various practical applications. In this paper, we present breakout local search (BLS) for solving QAP. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Experimental evaluations on the set of QAPLIB benchmark instances show that the proposed approach is able to attain current best-known results for all but two instances with an average computing time of less than 4.5 hours. Comparisons are also provided to show the competitiveness of the proposed approach with respect to the best-performing QAP algorithms from the literature. (C) 2012 Elsevier Inc. All rights reserved.