Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Discovering Popular Events on Twitter Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Weed Colonization Inspired Algorithm for the Weighted Set Cover Problem

verfasst von : Broderick Crawford, Ricardo Soto, Ismael Fuenzalida Legüe, Sanjay Misra, Eduardo Olguín

Erschienen in: Computational Science and Its Applications – ICCSA 2016

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The Weighted Set Cover Problem (SCP) is a popular optimization problem that has been applied to different industrial applications, including scheduling, manufacturing, service planning and location problems. It consists in to find low cost solutions covering a set of requirements or needs. In this paper, we solve the SCP using a recent nature inspired algorithm: Invasive Weed Optimization (IWO). IWO imitates the invasive behavior of real weeds: natural reproduction and selection where the best weed has more chance of reproduction. We test our approach using known ORLIB test problems for the SCP. The computational results show that the IWO metaheuristic can find very good results.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel A Type System for Android Applications
Nächstes Kapitel Software Architecture and Software Quality
Literatur
1.
Adulyasak, Y., Cordeau, J.-F., Jans, R.: The production routing problem: a review of formulations and solution algorithms. Comput. Oper. Res. 55, 141–152 (2015)MathSciNetCrossRefMATH
2.
Bai, R., Xue, N., Chen, J., Roberts, G.W.: A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem. Transp. Res. Part B: Methodol. 79, 134–148 (2015)CrossRef
3.
Beasley, J.E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)CrossRef
4.
Cacchiani, V., Hemmelmayr, V.C., Tricoire, F.: A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Appl. Math. 163, 53–64 (2014)MathSciNetCrossRefMATH
5.
6.
7.
Chen, S., Shen, Y.: An improved column generation algorithm for crew scheduling problems. J. Inf. Comput. Sci. 10(1), 175–183 (2013)
8.
Crawford, B., Soto, R., Aballay, F., Misra, S., Johnson, F., Paredes, F.: A teaching-learning-based optimization algorithm for solving set covering problems. 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. 9158, pp. 421–430. Springer, Heidelberg (2015)CrossRef
9.
Crawford, B., Soto, R., Cuesta, R., Paredes, F.: Application of the artificial bee colony algorithm for solving the set covering problem. Scientific World J. 2014, 8 (2014)CrossRef
10.
Crawford, B., Soto, R., Cuesta, R., Paredes, F.: Using the bee colony optimization method to solve the weighted set covering problem. In: Stephanidis, C. (ed.) HCI 2014, Part I. CCIS, vol. 434, pp. 493–497. Springer, Heidelberg (2014)CrossRef
11.
Crawford, B., Soto, R., Monfroy, E.: Cultural algorithms for the set covering problem. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI 2013, Part II. LNCS, vol. 7929, pp. 27–34. Springer, Heidelberg (2013)CrossRef
12.
Crawford, B., Soto, R., Olivares-Suárez, M., Palma, W., Paredes, F., Olguin, E., Norero, E.: A binary coded firefly algorithm that solves the set covering problem. Rom. J. Inf. Sci. Technol. 17(3), 252–264 (2014)
13.
Crawford, B., Soto, R., Peña, C., Riquelme-Leiva, M., Torres-Rojas, C., Johnson, F., Paredes, F.: Binarization methods for shuffled frog leaping algorithms that solve set covering problems. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Prokopova, Z., Silhavy, P. (eds.) CSOC2015. AISC, vol. 349, pp. 317–326. Springer, Heidelberg (2015)
14.
Crawford, B., Soto, R., Torres-Rojas, C., Peña, C., Riquelme-Leiva, M., Misra, S., Johnson, F., Paredes, F.: A binary fruit fly optimization algorithm to solve 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. 9158, pp. 411–420. Springer, Heidelberg (2015)CrossRef
15.
Elizondo-Amaya, M.G., RÃos-Mercado, R.Z., DÃaz, J.A.: A dual bounding scheme for a territory design problem. Comput. Oper. Res. 44, 193–205 (2014)MathSciNetCrossRefMATH
16.
Farahani, R.Z., Asgari, N., Heidari, N., Hosseininia, M., Goh, M.: Covering problems in facility location: a review. Comput. Ind. Eng. 62(1), 368–407 (2012)CrossRef
17.
Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2), 67–71 (1989)MathSciNetCrossRefMATH
18.
Juette, S., Thonemann, U.W.: Divide-and-price: a decomposition algorithm for solving large railway crew scheduling problems. Eur. J. Oper. Res. 219(2), 214–223 (2012)MathSciNetCrossRefMATH
19.
Mehrabian, A.R., Lucas, C.: A novel numerical optimization algorithm inspired from weed colonization. Ecol. Inform. 1(4), 355–366 (2006)CrossRef
20.
Revelle, C., Marks, D., Liebman, J.C.: An analysis of private and public sector location models. Manag. Sci. 16(11), 692–707 (1970)CrossRefMATH
21.
Schreuder, J.A.: Application of a location model to fire stations in rotterdam. Eur. J. Oper. Res. 6(2), 212–219 (1981)CrossRef
22.
Simeone, B., Nouno, G., Mezzadri, M., Lari, I.: A boolean theory of signatures for tonal scales. Discrete Appl. Math. 165, 283–294 (2014)MathSciNetCrossRefMATH
23.
Soto, R., Crawford, B., Galleguillos, C., Paredes, F., Norero, E.: A hybrid alldifferent-Tabu search algorithm for solving sudoku puzzles. Comput. Int. Neurosci. 2015, 286354:1–286354:10 (2015)
24.
Soto, R., Crawford, B., Muñoz, A., Johnson, F., Paredes, F.: Pre-processing, repairing and transfer functions can help binary electromagnetism-like algorithms. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Prokopova, Z., Silhavy, P. (eds.) Artificial Intelligence Perspectives and Applications. AISC, vol. 347, pp. 89–97. Springer, Heidelberg (2015)
25.
Toregas, C., Swain, R., ReVelle, C., Bergman, L.: The location of emergency service facilities. Oper. Res. 19(6), 1363–1373 (1971)CrossRefMATH
26.
Veenhuis, C.: Binary invasive weed optimization. In: 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC), pp. 449–454. IEEE (2010)
27.
Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231(1), 1–21 (2013)MathSciNetCrossRefMATH
28.
Walker, W.: Using the set-covering problem to assign fire companies to fire houses. Oper. Res. 22, 275–277 (1974)CrossRef
29.
Xu, Y., Kochenberger, G., Wang, H.: Pre-processing method with surrogate constraint algorithm for the set covering problem
30.
Zhang, J., Wei, Q., Chen, G.: A heuristic approach for \(\lambda \)-representative information retrieval from large-scale data. Inf. Sci. 277, 825–841 (2014)CrossRef
Metadaten
Titel
A Weed Colonization Inspired Algorithm for the Weighted Set Cover Problem
verfasst von
Broderick Crawford
Ricardo Soto
Ismael Fuenzalida Legüe
Sanjay Misra
Eduardo Olguín
Copyright-Jahr
2016
Buch
Computational Science and Its Applications – ICCSA 2016

Print ISBN: 978-3-319-42091-2

Electronic ISBN: 978-3-319-42092-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-42092-9_11