Top

Published in:

2018 | OriginalPaper | Chapter

Constructive Metaheuristics for the Set Covering Problem

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

Published in: Bioinspired Optimization Methods and Their Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Bio-inspired Approach for Collaborative Exploration with Mobile Battery Recharging in Swarm Robotics

next chapter Single and Multiobjective Evolutionary Algorithms for Clustering Biomedical Information with Unknown Number of Clusters

Aickelin, U.: An indirect genetic algorithm for set covering problems. J. Oper. Res. Soc. 53, 1118–1126 (2002)CrossRef

Beasley, J.: An algorithm for set covering problem. Eur. J. Oper. Res. 31, 85–93 (1987)MathSciNetCrossRef

Beasley, J.E., Chu, P.C.: A genetic algorithm for the set covering problem. Eur. J. Oper. Res. 94, 392–404 (1996)CrossRef

Brusco, M.J., Jacobs, L.W., Thompson, G.M.: A morphing procedure to supplement a simulated annealing heuristic for cost and coverage correlated set covering problems. Ann. Oper. Res. 86, 611–627 (1999)MathSciNetCrossRef

Crawford, B., Soto, R., Berríos, N., Johnson, F., Paredes, F., Castro, C., Norero, E.: A binary cat swarm optimization algorithm for the non-unicost set covering problem. In: Mathematical Problems in Engineering (2015)MathSciNetCrossRef

Crawford, B., Soto, R., Córdova, J., Olguín, E.: A nature inspired intelligent water drop algorithm and its application for solving the set covering problem. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Silhavy, P., Prokopova, Z. (eds.) Artificial Intelligence Perspectives in Intelligent Systems. AISC, vol. 464, pp. 437–447. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33625-1_39CrossRef

Crawford, B., Soto, R., Monfroy, E., Astorga, G., García, J., Cortes, E.: A meta-optimization approach for covering problems in facility location. In: Figueroa-García, J.C., López-Santana, E.R., Villa-Ramírez, J.L., Ferro-Escobar, R. (eds.) WEA 2017. CCIS, vol. 742, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66963-2_50CrossRef

Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 26(1), 29–41 (1996)CrossRef

Fisher, M., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Manag. Sci. 36(6), 674–688 (1990)MathSciNetCrossRef

10.

Hartmanis, J.: Computers and intractability: a guide to the theory of np-completeness (Michael R. Garey and David S. Johnson). SIAM Rev. 24(1), 90 (1982)CrossRef

11.

Lessing, L., Dumitrescu, I., Stützle, T.: A comparison between ACO algorithms for the set covering problem. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 1–12. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28646-2_1CrossRef

12.

Shah-Hosseini, H.: Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem. Int. J. Intell. Comput. Cybern. 1(2), 193–212 (2008)MathSciNetCrossRef

13.

Soto, R., Crawford, B., Galleguillos, C., Barraza, J., Lizama, S., Muñoz, A., Vilches, J., Misra, S., Paredes, F.: Comparing cuckoo search, bee colony, firefly optimization, and electromagnetism-like algorithms for solving the set covering problem. In: Gervasi, O., Murgante, B., Misra, S., Gavrilova, M.L., Rocha, A.M.A.C., Torre, C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2015. LNCS, vol. 9155, pp. 187–202. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21404-7_14CrossRef

Title: Constructive Metaheuristics for the Set Covering Problem
Authors: Broderick Crawford
Ricardo Soto
Gino Astorga
José García
Publisher: Springer International Publishing
Book: Bioinspired Optimization Methods and Their Applications
Print ISBN: 978-3-319-91640-8

Electronic ISBN: 978-3-319-91641-5

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-91641-5_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner