Constructive metaheuristics for the set covering problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationBioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings
EditorsNouredine Melab, Peter Korosec, El-Ghazali Talbi
PublisherSpringer Verlag
Pages88-99
Number of pages12
ISBN (Print)9783319916408
DOIs
StatePublished - 1 Jan 2018
Event8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018 - Paris, France
Duration: 16 May 201818 May 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10835 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018
CountryFrance
CityParis
Period16/05/1818/05/18

Keywords

  • Constructive metaheuristic
  • Intelligent Water Drops
  • Set Covering Problem

Fingerprint Dive into the research topics of 'Constructive metaheuristics for the set covering problem'. Together they form a unique fingerprint.

Cite this