A Selector Operator-Based Adaptive Large Neighborhood Search for the Covering Tour Problem
A Selector Operator-Based Adaptive Large Neighborhood Search for the Covering Tour Problem
复制标题
基于选择算子的自适应大邻域搜索覆盖巡视问题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Ngueveu
中科院分区：
文献类型：
--
作者：
Leticia Vargas;Nicolas Jozefowiez;S. Ngueveu
覆盖线路问题在配电网设计中得到了应用。它包括两种类型的顶点：覆盖的顶点和被覆盖的顶点。这个问题是关于在覆盖点的子集上确定一个代价最低的哈密顿循环，在这种情况下，所有不是这种类型的元素都被覆盖。在这种情况下，当一个顶点位于给定的距离内时，就认为它被覆盖了。本文提出了一个基于选择算子的求解过程，该过程允许将一个巨游转换为最优CTP解。该算子嵌入到自适应大邻域搜索中。该方法具有竞争力，通过使用最先进的精确算法的输出来评估结果的质量。
The Covering Tour Problem finds application in distribution network design. It includes two types of vertices: the covering ones and the ones to be covered. This problem is about identifying a lowest-cost Hamiltonian cycle over a subset of the covering vertices in such a way that every element not of this type is covered. In this case, a vertex is considered covered when it is located within a given distance from a vertex in the tour. This paper presents a solution procedure based on a Selector operator that allows to convert a giant tour into an optimal CTP solution. This operator is embedded in an adaptive large neighborhood search. The method is competitive as shown by the quality of results evaluated using the output of a state-of-the-art exact algorithm.