학술논문
MLQCC: an improved local search algorithm for the set $k$-covering problem.
Document Type
Journal
Author
Wang, Yiyuan (PRC-NNU-CIT) AMS Author Profile; Li, Chenxi (PRC-NNU-CIT) AMS Author Profile; Sun, Huanyao (PRC-NNU-CIT) AMS Author Profile; Chen, Jiejiang (PRC-NNU-CIT) AMS Author Profile; Yin, Minghao (PRC-NNU-CIT) AMS Author Profile
Source
Subject
90 Operations research, mathematical programming -- 90C Mathematical programming
90C59Approximation methods and heuristics
90C59
Language
English
ISSN
14753995
Abstract
Summary: ``The set $k$-covering problem (SKCP) is NP-hard and hasimportant real-world applications. In this paper, we propose severalimprovements over typical algorithms for its solution. First, wepresent a multilevel (ML) score heuristic that reflects relevantinformation of the currently selected subsets inside or outside acandidate solution. Next, we propose QCC to overcome the cyclingproblem in local search. Based on the ML heuristic and QCC strategy, wepropose an effective subset selection strategy. Then, we integratethese methods into a local search algorithm, which we called MLQCC. Inaddition, we propose a preprocessing method to reduce the scale of theoriginal problem before applying MLQCC. We further enhance MLQCC forlarge-scale instances using a low-time-complexity initializationalgorithm to determine an initial candidate solution, obtaining the$\rm MLQCC + LI$ algorithm. The performance of the proposed MLQCC and$\rm MLQCC + LI$ is verified through experimental evaluations on bothclassical and large-scale benchmarks. The results show that MLQCC and$\rm MLQCC + LI$ notably outperform several state-of-the-art SKCPalgorithms on the evaluated benchmarks.''