Bee colony optimization for the \(p\)-center problem.

*(English)*Zbl 1208.90103Summary: Bee colony optimization (BCO) is a relatively new meta-heuristic designed to deal with hard combinatorial optimization problems. It is biologically inspired method that explores collective intelligence applied by the honey bees during nectar collecting process. In this paper we apply BCO to the \(p\)-center problem in the case of symmetric distance matrix. On the contrary to the constructive variant of the BCO algorithm used in recent literature, we propose variant of BCO based on the improvement concept (BCOi). The BCOi has not been significantly used in the relevant BCO literature so far. In this paper it is proved that BCOi can be a very useful concept for solving difficult combinatorial problems. The numerical experiments performed on well-known benchmark problems show that the BCOi is competitive with other methods and it can generate high-quality solutions within negligible CPU times.

##### MSC:

90B80 | Discrete location and assignment |

90C59 | Approximation methods and heuristics in mathematical programming |

90C35 | Programming involving graphs or networks |

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Keywords:

meta-heuristics; bee colony optimization; combinatorial optimization; location analysis; \(p\)-center problem
PDF
BibTeX
XML
Cite

\textit{T. Davidović} et al., Comput. Oper. Res. 38, No. 10, 1367--1376 (2011; Zbl 1208.90103)

Full Text:
DOI

##### References:

[1] | Lučić P, Teodorović D. Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence. In: Preprints of the TRISTAN IV triennial symposium on transportation analysis, Sao Miguel, Azores Islands; 2001. p. 441-5. |

[2] | Lučić P, Teodorović D. Transportation modeling: an artificial life approach. In: Proceedings of the 14th IEEE international conference on tools with artificial intelligence, Washington, DC; 2002. p. 216-23. |

[3] | Lučić, P.; Teodorović, D., Computing with bees: attacking complex transportation engineering problems, International journal on artificial intelligence tools, 12, 375-394, (2003) |

[4] | Lučić, P.; Teodorović, D., Vehicle routing problem with uncertain demand at nodes: the bee system and fuzzy logic approach, (), 67-82 · Zbl 1051.90009 |

[5] | Marković, G.; Teodorović, D.; Aćimović-Raspopović, V., Routing and wavelength assignment in all-optical networks based on the bee colony optimization, AI communications, 20, 273-285, (2007) · Zbl 1185.90174 |

[6] | Teodorović, D.; Dell’Orco, M., Mitigating traffic congestion: solving the ride-matching problem by bee colony optimization, Transportation planning and technology, 31, 135-152, (2008) |

[7] | Edara P, Šelmić M, Teodorović D. Heuristic solution algorithms for a traffic sensor optimization problem. In: INFORMS 2008, Washington, DC; 2008. |

[8] | Davidović T, Šelmić M, Teodorović D. Scheduling independent tasks: bee colony optimization approach. In: Proceedings of the 17th Mediterranean conference on control and automation, Makedonia Palace, Thessaloniki, Greece; 2009. p. 1020-5. |

[9] | Hakimi, S.L., Optimal locations of switching centers and the absolute centers and medians of a graph, Operations research, 12, 450-459, (1964) · Zbl 0123.00305 |

[10] | Hakimi, S.L., Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations research, 13, 3, 462-475, (1965) · Zbl 0135.20501 |

[11] | Minieka, E., The centers and medians of a graph, Operations research, 25, 4, 641-650, (1977) · Zbl 0383.90046 |

[12] | Drezner, Z., The planar two center and two Median problems, Transportation science, 18, 451-461, (1984) |

[13] | Beasly, J.E., A note on solving large p-Median problems, European journal of operational research, 21, 270-273, (1985) · Zbl 0569.90021 |

[14] | Hassin, R.; Levin, M.; Morad, D., Lexicographic local search and the p-center problem, European journal of operational research, 151, 265-279, (2003) · Zbl 1053.90052 |

[15] | Mladenović, N.; Labbe, M.; Hansen, P., Solving the p-center problem with tabu search and variable neighborhood search, Networks, 42, 1, 48-64, (2003) · Zbl 1036.90046 |

[16] | Caruso, C.; Colorni, A.; Aloi, L., Dominant, an algorithm for the p-center problem, European journal of operational research, 149, 1, 53-64, (2003) · Zbl 1035.90037 |

[17] | Pacheco, J.A.; Casado, S., Solving two location models with few facilities by using a hybrid heuristic: a real health resources case, Computers & operations research, 32, 12, 3075-3091, (2005) · Zbl 1146.90460 |

[18] | ReVelle, C.; Eiselt, H., Location analysis: a synthesis and survey, European journal of operational research, 165, 1, 1-19, (2005) · Zbl 1112.90362 |

[19] | Chen, D.; Chen, R., New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems, Computers & operations research, 36, 5, 1646-1655, (2009) · Zbl 1177.90246 |

[20] | Bonabeau, E.; Dorigo, M.; Theraulaz, G., Swarm intelligence, (1997), Oxford University Press Oxford |

[21] | Dorigo, M.; Stützle, T., Ant colony optimization, (2004), The MIT Press · Zbl 1092.90066 |

[22] | Kennedy, J.; Eberhart, R., Particle swarm optimization, (), 1942-1948 |

[23] | Yonezawa Y, Kikuchi T. Ecological algorithm for optimal ordering used by collective honey bee behavior. In: Proceedings of the seventh international symposium on micro machine and humane science, Nagoya, Japan; 1995. p. 249-55. |

[24] | Sato T, Hagiwara M. Bee system: finding solution by a concentrated search. In: Proceedings of the IEEE international conference on systems, man, and cybernetics ‘computational cybernetics and simulation’, Orlando, FL, USA; 1997. p. 3954-9. |

[25] | Abbass HA. MBO: marriage in honey bees optimization-a haplometrosis polygynous swarming approach. In: Proceedings of the congress on evolutionary computation, Seoul, South Korea; 2001. p. 207-14. |

[26] | Wedde, H.F.; Farooq, M.; Zhang, Y., Beehive: an efficient fault-tolerant routing algorithm inspired by honey bee behavior, (), 83-94 |

[27] | Wedde, H.F.; Timm, C.; Farooq, M., Beehiveais: a simple, efficient, scalable and secure routing framework inspired by artificial immune systems, (), 623-632 |

[28] | Wedde HF, Sebastian L, Bernhard van B, Zeynep B. A novel class of multi-agent algorithms for highly dynamic transport planning inspired by honey bee behavior. In: Proceedings of the 12th IEEE international conference on factory automation, Patras, Greece; 2007. p. 1157-64. |

[29] | Karaboga D. An idea based on honey bee swarm for numerical optimization. Technical Report, Erciyes University, Engineering Faculty Computer Engineering Department Kayseri/Turkiye; 2005. |

[30] | Karaboga, D.; Basturk, 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 |

[31] | Karaboga, D.; Basturk, B., On the performance of artificial bee colony algorithm, Applied soft computing, 8, 687-697, (2008) |

[32] | Pham, D.T.; Ghanbarzadeh, A.; Koc, E.; Otri, S.; Zaidi, M., The bees algorithm—a novel tool for complex optimisation problems, (), 454-459 |

[33] | Pham DT, Soroka AJ, Ghanbarzadeh A, Koc E. Optimising neural networks for identification of wood defects using the bees algorithm. In: Proceedings of the IEEE international conference on industrial informatics, Singapore; 2006, pp. 1346-51. |

[34] | Pham, D.T.; Haj Darwish, A.; Eldukhr, E.E., Optimisation of a fuzzy logic controller using the bees algorithm, International journal of computer-aided engineering technology, 250-264, (2009) |

[35] | Karaboga, D.; Akay, B., A survey: algorithms simulating bee swarm intelligence, Artificial intelligence review, 31, 61-85, (2009) |

[36] | Teodorović, D., Bee colony optimization (BCO), (), 39-60 |

[37] | Camazine, S.; Sneyd, J., A model of collective nectar source by honey bees: self-organization through simple rules, Journal of theoretical biology, 149, 547-571, (1991) |

[38] | Teodorović D, Davidović T, Šelmić M, Ramljak D. An application of a meta-heuristic algorithm to p-center location problem. In: Proceedings of the symposium on information technology, YUINFO, Kopaonik, Serbia (in Serbian on CD 026.pdf); 2010. |

[39] | Lawler, E., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston · Zbl 0413.90040 |

[40] | Daskin, M., Network and discrete location: models, algorithms, and application, (1995), John Wiley & Sons |

[41] | Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems. part ii. the p-Median, SIAM journal of applied mathematics, 37, 539-560, (1969) · Zbl 0432.90075 |

[42] | Handler, G.Y., p-center problems, (), 305-347 |

[43] | Chandrasekaran, R.; Tamir, A., Polynomial bounded algorithms for locating p-centers on a tree, Mathematical programming, 22, 304-315, (1982) · Zbl 0486.90036 |

[44] | Pelgrin, B., Heuristic methods for the p-center problem, RAIRO recherche operationelle, 25, 65-72, (1991) |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.