×

Bees algorithm for generalized assignment problem. (English) Zbl 1181.90167

Summary: Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
90C10 Integer programming

Software:

Tabu search; ABC
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Martello, S.; Toth, P., An algorithm for the generalized assignment problems, (Brans, J. P., Operational Research (1981), North-Holland), 589-603
[3] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley New York · Zbl 0708.68002
[5] Cattrysse, D.; Salomon, M.; Van Wassenhove, L. N., A set partitioning heuristic for the generalized assignment problem, European Journal of Operational Research, 72, 167-174 (1994) · Zbl 0798.90107
[6] Ross, G. T.; Soland, P. M., A branch and bound based algorithm for the generalized assignment problem, Mathematical Programming, 8, 91-103 (1975) · Zbl 0308.90028
[7] Fisher, M. L.; Jaikumar, R.; Van Wassenhove, L. N., A multiplier adjustment method for the generalized assignment problem, Management Science, 32, 1095-1103 (1986) · Zbl 0626.90036
[8] Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Operations Research, 45, 831-841 (1997) · Zbl 0895.90161
[9] Nauss, R. M., Solving the generalized assignment problem: an optimizing and heuristic approach, Informs Journal of Computing, 15, 249-266 (2003) · Zbl 1238.90090
[10] Osman, I. H., Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches, OR Spektrum, 17, 211-225 (1995) · Zbl 0841.90098
[11] Chu, P. C.; Beasley, J. E., A genetic algorithm for the generalized assignment problem, Computers and Operations Research, 24, 17-23 (1997) · Zbl 0881.90070
[12] Racer, M.; Amini, M. M., A robust heuristic for the generalized assignment problem, Annals of Operations Research, 50, 487-503 (1994) · Zbl 0812.90097
[13] Yagiura, M.; Yamaguchi, T.; Ibaraki, T., A variable-depth search algorithm with branching search for the generalized assignment problem, Optimization Methods and Software, 10, 419-441 (1998) · Zbl 0947.90070
[14] Yagiura, M.; Yamaguchi, T.; Ibaraki, T., A variable-depth search algorithm for the generalized assignment problem, (Vob, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 459-471 · Zbl 0985.90079
[15] Laguna, M.; Kelly, J. P.; Gonzalez-Velarde, J. L.; Glover, F., Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research, 82, 176-189 (1995) · Zbl 0905.90122
[16] Diaz, J. A.; Fernandez, E., A tabu search heuristic for the generalized assignment problem, European Journal Operational Research, 132, 22-38 (2001) · Zbl 0980.90045
[17] Yagiura, M.; Ibaraki, T.; Glover, F., An ejection chain approach for the generalized assignment problem, Informs Journal of Computing, 16, 131-151 (2004) · Zbl 1239.90091
[18] Lourenço, H. R.; Serra, D., Adaptive search heuristics for the generalized assignment problem, Mathware and Soft Computing, 9, 209-234 (2002) · Zbl 1031.68056
[21] Alfandari, L.; Plateau, A.; Tolla, P., A path relinking algorithm for the generalized assignment problem, (Resende, M. G.C.; Sousa, J. D., Metaheuristics: Computer Decision-Making (2004), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 1-17
[24] Yagiura, M.; Ibaraki, T.; Glover, F., A path relinking approach with ejection chains for the generalized assignment problem, European Journal of Operational Research, 169, 548-569 (2006) · Zbl 1079.90119
[28] Seeley, T. D., The Wisdom of the Hive (1995), Harvard University Press: Harvard University Press Cambridge, MA
[31] Lucic, P.; Teodorovic, D., Computing with bees: attacking complex transportation engineering problems, International Journal on Artificial Intelligence Tools, 12, 3, 375-394 (2003)
[33] Lucic, P.; Teodorovic, D., Vehicle routing problem with uncertain demand at nodes: the bee system and fuzzy logic approach, (Verdegay, J. L., Fuzzy Sets in Optimization (2003), Springer-Verlag: Springer-Verlag Berlin Heidelbelg), 67-82 · Zbl 1051.90009
[35] Markovic, G. Z.; Teodorovic, D.; Acimovic-Raspopovic, V. S., Routing and wavelength assignment in all-optical networks based on the bee colony optimization, AI Communications, 20, 4, 273-285 (2007) · Zbl 1185.90174
[37] Wedde, H. F.; Farooq, M.; Zhang, Y., BeeHive: an efficient fault-tolerant routing algorithm inspired by honey bee behavior, Lecture Notes in Computer Science, 3172, 83-94 (2004)
[40] Drias, H.; Sadeg, S.; Yahi, S., Cooperative bees swarm for solving the maximum weighted satisfiability problem, Lecture Notes in Computer Science, 3512, 318-325 (2005)
[43] Karaboğa, D.; Baştürk, B., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of Global Optimization, 39, 459-471 (2007) · Zbl 1149.90186
[44] Yang, X. S., Engineering optimizations via nature-inspired virtual bee algorithms, Lecture Notes in Computer Science, 3562, 317-323 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.