TY - GEN
T1 - Constructive metaheuristics for the set covering problem
AU - Crawford, Broderick
AU - Soto, Ricardo
AU - Astorga, Gino
AU - García, José
N1 - Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the problem considered.
AB - Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the problem considered.
KW - Constructive metaheuristic
KW - Intelligent Water Drops
KW - Set Covering Problem
UR - http://www.scopus.com/inward/record.url?scp=85047450375&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-91641-5_8
DO - 10.1007/978-3-319-91641-5_8
M3 - Conference contribution
AN - SCOPUS:85047450375
SN - 9783319916408
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 88
EP - 99
BT - Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings
A2 - Melab, Nouredine
A2 - Korosec, Peter
A2 - Talbi, El-Ghazali
PB - Springer Verlag
T2 - 8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018
Y2 - 16 May 2018 through 18 May 2018
ER -