.png){kind=icon}
.png){kind=icon}
Return
A New Direct Coefficient-Based Heuristic Algorithm for Set Covering Problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s40815-021-01208-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The set covering problem is a fundamental model which comprises a wide range of important applications such as crew scheduling problems that need to cover a set of trips. It is one of the most common issues in the facility location problem, which requires further investigations, particularly in emergency and service facilities. As such, the objective of this study is to propose a new coefficient-based heuristic algorithm for the set covering problems. This paper has accordingly presented the algorithm that evaluates the qualification of subsets by directly applying a fitness function. This fitness function is formulated based on sets and subsets coefficients in a way that the subsets of selected sets have the lowest probability to be selected in the next iteration. The algorithm is not only capable of constructing an answer within polynomial time, but can solve complex set covering problems without conventional restrictions. The performance of this algorithm is evaluated on benchmark instances including a set of reproduced and selected OR-library problems within different sizes. Computational results indicate that the proposed heuristic algorithm produces better solutions, especially in large-scale problems comparing simulated annealing in terms of quality and time.
Keywords:
Set covering problem
Heuristic algorithm
Coefficient
Optimization
Journal
IF:
3.6
Papers:
2.2K
Citations:
4.3K
View more organizations