Constructive metaheuristics for the set covering problem

Broderick Crawford; Ricardo Soto; Gino Astorga; José García

doi:10.1007/978-3-319-91641-5_8

Constructive metaheuristics for the set covering problem

Broderick Crawford, Ricardo Soto, Gino Astorga, José García

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

19 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 language	English
Title of host publication	Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings
Editors	Nouredine Melab, Peter Korosec, El-Ghazali Talbi
Publisher	Springer Verlag
Pages	88-99
Number of pages	12
ISBN (Print)	9783319916408
DOIs	https://doi.org/10.1007/978-3-319-91641-5_8
State	Published - 2018
Event	8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018 - Paris, France Duration: 16 May 2018 → 18 May 2018

Publication series

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

Conference

Conference	8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018
Country/Territory	France
City	Paris
Period	16/05/18 → 18/05/18

Keywords

Constructive metaheuristic
Intelligent Water Drops
Set Covering Problem

Access to Document

10.1007/978-3-319-91641-5_8

Cite this

Crawford, B., Soto, R., Astorga, G., & García, J. (2018). Constructive metaheuristics for the set covering problem. In N. Melab, P. Korosec, & E-G. Talbi (Eds.), Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings (pp. 88-99). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10835 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-91641-5_8

Crawford, Broderick ; Soto, Ricardo ; Astorga, Gino et al. / Constructive metaheuristics for the set covering problem. Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings. editor / Nouredine Melab ; Peter Korosec ; El-Ghazali Talbi. Springer Verlag, 2018. pp. 88-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9ad6fe54f936448f95536ea5d5584b54,

title = "Constructive metaheuristics for the set covering problem",

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.",

keywords = "Constructive metaheuristic, Intelligent Water Drops, Set Covering Problem",

author = "Broderick Crawford and Ricardo Soto and Gino Astorga and Jos{\'e} Garc{\'i}a",

note = "Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018 ; Conference date: 16-05-2018 Through 18-05-2018",

year = "2018",

doi = "10.1007/978-3-319-91641-5_8",

language = "English",

isbn = "9783319916408",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "88--99",

editor = "Nouredine Melab and Peter Korosec and El-Ghazali Talbi",

booktitle = "Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings",

}

Crawford, B , Soto, R, Astorga, G & García, J 2018, Constructive metaheuristics for the set covering problem. in N Melab, P Korosec & E-G Talbi (eds), Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10835 LNCS, Springer Verlag, pp. 88-99, 8th International Conference on Bioinspired Optimization Methods and Their Applications, BIOMA 2018, Paris, France, 16/05/18. https://doi.org/10.1007/978-3-319-91641-5_8

Constructive metaheuristics for the set covering problem. / Crawford, Broderick ; Soto, Ricardo; Astorga, Gino et al.
Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings. ed. / Nouredine Melab; Peter Korosec; El-Ghazali Talbi. Springer Verlag, 2018. p. 88-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10835 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Constructive metaheuristics for the set covering problem

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Astorga, Gino

AU - García, José

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 -

Crawford B , Soto R, Astorga G, García J. Constructive metaheuristics for the set covering problem. In Melab N, Korosec P, Talbi E-G, editors, Bioinspired Optimization Methods and Their Applications - 8th International Conference, BIOMA 2018, Proceedings. Springer Verlag. 2018. p. 88-99. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-91641-5_8

Constructive metaheuristics for the set covering problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this