.png){kind=icon}
返回
An improved configuration checking-based algorithm for the unicost set covering problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2021.02.015.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Configuration Checking (CC) is a simple tool that can be added to local search algorithms to prevent cycling. The generic forms of CC and local search may not be suitable to solve large-scale unicost set covering problem (USCP) instances. Thus, in this study, we introduce an improved CC-based algorithm to solve USCPs. Unlike previous CC implementations that only consider subset states to prevent cycling, the proposed algorithm also checks the element states to minimize the number of subsets, in order to cut down unnecessary search spaces. Therefore, we refer to this technique as the element-state configuration checking (ES-CC) algorithm. Moreover, in our proposed algorithm, the score value (a numerical measure to differentiate between subsets) considers multiple levels of element covering. This multi-level scoring (MLS) value is a new powerful contribution compared to the single-level scoring used in previous CC algorithms. Using these two novel ideas, MLS and ES-CC, we implement the new MLSES-CC algorithm to solve the USCP. The MLSES-CC algorithm also implements a more aggressive local search routine that simultaneously changes the status of the three subsets. We use the MLSES-CC algorithm to solve 176 USCP instances that belong to standard and novel benchmarking sets and compare our results to the bestknown USCP algorithms, in terms of solution quality and computation time. Computational experiments indicate that the MLSES-CC algorithm can be considered as a new state-of-the-art algorithm to solve USCPs. (c) 2021 Elsevier B.V. All rights reserved.
Keyword:
Combinatorial optimization
Unicost set covering
Local search
Multi-level scoring function
Element state-based configuration checking
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
An efficient local search heuristic with row weighting for the unicost set covering problem用于unicost集覆盖问题的具有行加权的有效局部搜索启发式方法
PREAI
分享收藏Performance Evaluation of Three Mobile Ad-hoc Network Routing Protocols in Different Environments
PREAI
分享收藏Extracting flame describing functions in the presence of self-excited thermoacoustic oscillations
OAAI
OAAI分享收藏
查看更多内容