带节点与线段的覆盖旅行商问题的破坏-修复启发式算法

《Algorithms》：A Destroy-and-Repair Heuristic for the Covering Salesman Problem with Nodes and Segments

　　摘 要带节点与线段的覆盖旅行商问题（CSPNS）通过允许从访问节点或路径线段覆盖目标，扩展了旅行商问题。受无人机监测和灾后信息采集应用的启发，本研究提出了一种用于CSPNS的破坏-修复（DR）启发式算法。该算法通过局部破坏与修复过程重构访问节点集合和游览路线，利用节点与线段覆盖恢复可行性，并采用CSPNS局部搜索进行优化。将所提方法的性能与局部搜索、多起点局部搜索（MSLS）和禁忌搜索（TS）进行比较。对于每种规模-半径设定，使用一个训练实例选择破坏-修复组合及破坏率，并在四个独立实例上评估所选配置，每个实例运行100次试验。MSLS、TS和DR使用相同的每次试验CPU时间限制。对于100节点和150节点问题，DR在设定层面的平均参考间隙小于TS。采用Holm校正的双侧精确Wilcoxon符号秩检验显示，在所有16组DR-TS比较中均存在显著差异，其中14组有利于DR，2组有利于TS。DR在所有16个评估实例中也显著优于MSLS。对于200节点和300节点问题，在每种规模-半径设定下对评估实例取平均时，DR的平均路线成本低于MSLS和TS。额外实验在相同训练和评估协议下比较了均匀算子和自适应算子选择。这些比较未发现自适应算子权重在测试条件下相比均匀选择具有一致优势。上述结果支持了所提出的DR启发式算法在CSPNS中的有效性。