信息工程大学学报2024，Vol.25Issue(1)：58-64,7.DOI:10.3969/j.issn.1671-0673.2024.01.009
基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题
Iterative Local Search Algorithm Based on Multi-vertex Substitution Strategy for the Covering Salesman Problem
摘要
Abstract
Covering salesman problem(CSP)is an extension of the famous traveling salesman prob-lem,which is NP-hard problem.Given a set of vertices and a predetermined coverage radius associ-ated 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 lo-cal search algorithm to solve CSP.Our algorithm explores neighborhood optimal solutions through it-erative perturbation procedures,in which the perturbation process diverges the search into unex-plored 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.关键词
覆盖推销员问题/旅行商问题/迭代局部搜索/启发式算法Key words
covering salesman problem/traveling salesman problem/iterated local search/heuristic algorithm分类
数理科学引用本文复制引用
武艳宇,成毅,葛文..基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题[J].信息工程大学学报,2024,25(1):58-64,7.
