A Destroy-and-Repair Heuristic for the Covering Salesman Problem with Nodes and Segments

The covering salesman problem with nodes and segments (CSPNS) extends the traveling salesman problem by allowing targets to be covered from visited nodes or route segments. Motivated by drone-based monitoring and information collection after disasters, this study investigates a destroy-and-repair (DR) heuristic for CSPNS. The heuristic reconstructs both the visited-node set and the tour through partial destruction and repair, restores feasibility using node and segment coverage, and applies CSPNS local search. The performance of the proposed method is compared with local search, multi-start local search (MSLS), and tabu search (TS). The destroy–repair combination and destruction rate are selected using one training instance per size–radius setting, and the selected configuration is evaluated on four separate instances using 100 trials per instance. MSLS, TS, and DR use equal per-trial CPU-time limits. For 100-node and 150-node problems, DR obtains smaller setting-level average reference gaps than TS. Two-sided exact Wilcoxon signed-rank tests with the Holm correction show significant differences in all 16 DR–TS comparisons, favoring DR in 14 cases and TS in two. DR also significantly outperforms MSLS in all 16 evaluation instances. For 200-node and 300-node problems, DR obtains lower mean route costs than both MSLS and TS when averaged over the evaluation instances in each size–radius setting. Additional experiments compare uniform and adaptive operator selection under the same training and evaluation protocol. These comparisons find no consistent advantage of adaptive operator weighting over uniform selection under the tested conditions. These results support the effectiveness of the proposed DR heuristic for CSPNS.