کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479491 | 1445997 | 2015 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An efficient local search heuristic with row weighting for the unicost set covering problem An efficient local search heuristic with row weighting for the unicost set covering problem](/preview/png/479491.png)
• A new algorithm was developed for the unicost set covering problem.
• It integrates ideas of adaptive row weighting, a tabu list, and timestamps.
• It was evaluated on 91 benchmark problems with up to millions of variables.
• It improved the best known solutions on 14 problems.
The Set Covering Problem (SCP) is NPNP-hard. We propose a new Row Weighting Local Search (RWLS) algorithm for solving the unicost variant of the SCP, i.e., USCPs where the costs of all sets are identical. RWLS is a heuristic algorithm that has three major components united in its local search framework: (1) a weighting scheme, which updates the weights of uncovered elements to prevent convergence to local optima, (2) tabu strategies to avoid possible cycles during the search, and (3) a timestamp method to break ties when prioritizing sets. RWLS has been evaluated on a large number of problem instances from the OR-Library and compared with other approaches. It is able to find all the best known solutions (BKS) and improve 14 of them, although requiring a higher computational effort on several instances. RWLS is especially effective on the combinatorial OR-Library instances and can improve the best known solution to the hardest instance CYC11 considerably. RWLS is conceptually simple and has no instance-dependent parameters, which makes it a practical and easy-to-use USCP solver.
Journal: European Journal of Operational Research - Volume 246, Issue 3, 1 November 2015, Pages 750–761