基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题

Iterative Local Search Algorithm Based on Multi-vertex Substitution Strategy for the Covering Salesman Problem

覆盖推销员问题(Covering Salesman Problem,CSP)是著名的旅行商问题的一个变体,是NP难问题。给定一组顶点和每个顶点相关联的预定覆盖半径,CSP的目标是在顶点子集上找到一个最短长度的哈密顿回路,使每个顶点被访问或者在被访问顶点的覆盖范围内。为提升搜索候选顶点集的质量,提出一种基于多顶点替换的搜索策略,并将该策略引入到迭代局部搜索算法解决CSP。所提CSP算法通过扰动过程和改进过程的迭代探索邻域最优解,其中扰动过程将搜索发散到未探索的区域,改进过程提升解的质量。实验结果表明,多顶点替换方法相比“移出-重新插入”过程可以获得更高质量的候选顶点集。所提CSP算法在寻优的正确率上取得了不错的成效,尽管运行速度与其他启发式算法相比有差距,但可以在合理的运行时间内解决CSP。

Covering salesman problem(CSP)is an extension of the famous traveling salesman problem,which is NP-hard problem.Given a set of vertices and a predetermined coverage radius associated with each vertex,the goal of CSP is to find a Hamiltonian circle of the shortest length over a subset of vertices,so that each vertex is visited or within the coverage of at least one vertex included in the cycle.To improve the search quality of candidate vertex sets,we propose a candidate vertex set search strategy based on multi-vertex substitution,and introduce this strategy into the iterative local search algorithm to solve CSP.Our algorithm explores neighborhood optimal solutions through iterative perturbation procedures,in which the perturbation process diverges the search into unexplored regions,and improvement procedures improve the quality of the solutions.The experimental results show that the multi-vertex replacement method can obtain a higher quality candidate vertex set compared with“remove-reinsert”process.The iterative local search algorithm with multi-vertex replacement strategy has achieved good results in the search accuracy,and can solve the CSP in a reasonable running time,but the running speed still lags behind that of other heuristic algorithms.