Mei Yi, Tang Ke, Yao Xin
Nature Inspired Computation and Applications Laboratory, Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China.
IEEE Trans Syst Man Cybern B Cybern. 2009 Jun;39(3):723-34. doi: 10.1109/TSMCB.2008.2008906. Epub 2009 Feb 10.
Capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable for small instances, heuristics and metaheuristic methods are widely adopted when solving CARP. This paper demonstrates one major disadvantage encountered by traditional search algorithms and proposes a novel operator named global repair operator (GRO) to address it. We further embed GRO in a recently proposed tabu search algorithm (TSA) and apply the resultant repair-based tabu search (RTS) algorithm to five well-known benchmark test sets. Empirical results suggest that RTS not only outperforms TSA in terms of quality of solutions but also converges to the solutions faster. Moreover, RTS is also competitive with a number of state-of-the-art approaches for CARP. The efficacy of GRO is thereby justified. More importantly, since GRO is not specifically designed for the referred TSA, it might be a potential tool for improving any existing method that adopts the same solution representation.
容量受限弧路由问题（CARP）在过去几年中因其在现实生活中的广泛应用而备受关注。由于CARP是NP难问题，精确方法仅适用于小规模实例，因此在求解CARP时广泛采用启发式和元启发式方法。本文展示了传统搜索算法遇到的一个主要缺点，并提出了一种名为全局修复算子（GRO）的新算子来解决这一问题。我们进一步将GRO嵌入到最近提出的禁忌搜索算法（TSA）中，并将由此产生的基于修复的禁忌搜索（RTS）算法应用于五个著名的基准测试集。实证结果表明，RTS不仅在解的质量方面优于TSA，而且收敛到解的速度更快。此外，RTS在解决CARP问题上也与许多先进方法具有竞争力。GRO的有效性由此得到证明。更重要的是，由于GRO不是专门为所提及的TSA设计的，它可能是改进任何采用相同解表示的现有方法的潜在工具。
