بهینه سازی کلونی زنبور عسل برای مسئله P-Center

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.

Meta-heuristics have become very powerful tool for solving hard combinatorial optimization problems. Among them a class of biologically inspired algorithms can be recognized. Bee colony optimization (BCO) method, that explores collective intelligence applied by the honey bees during nectar collecting process, is one of them. BCO has been proposed by Lučić and Teodorović [1], [2] and [3] and up to now it is successfully applied to various real-life optimization problems. The BCO is a stochastic, random-search technique that belongs to the class of population-based algorithms. This technique uses an analogy between the way in which bees in nature search for food, and the way in which optimization algorithms search for an optimum of (given) combinatorial optimization problems. Since its appearance it had various successful applications. BCO has been proposed for the first time in [1], [2] and [3] for solving the travelling salesman problem and was evolving through later applications. The BCO has also been applied to: the vehicle routing problem [4], the routing and wavelength assignment (RWA) in all-optical networks [5], the ride-matching problem [6], the traffic sensors locations problem on highways [7], and the static scheduling of independent tasks on homogeneous multiprocessor systems [8]. In this paper we develop a new version of the BCO algorithm to deal with the problem of locating p centers on a network of n vertices (p-center problem) with symmetric distance matrix. Center problems in location analysis are the problems related to the location of emergency-type facilities (centers) in the transportation networks. Ambulance, fire and police departments all over the world have numerous facilities (fire stations, police stations, ambulances depots). Proper location of these facilities, as well as adequate vehicle dispatching strategy has a crucial influence on a survival rate of citizens who are in emergency-type situations. For emergency services, the location of the facilities must be such as to minimize the furthest distance (time) that the vehicles will ever travel when responding to an emergency call. The importance of this issue is reflected in the large number of papers that consider the location of centers [9], [10], [11], [12], [13], [14], [15], [16], [17], [18] and [19]. To approach the p-center problem, we propose an artificial system composed of a number of precisely defined agents (individuals, artificial bees). Multi-agent simulation is performed, i.e. we specify behavior rules of our agents and simulate the interaction between them (the way in which agents communicate with each other). Our model and a corresponding computer program determine the way our agents perform their activities. Various behavior rules lead us to different variants of BCO algorithms. Two variants of the BCO algorithm can be distinguished straightforward: constructive BCO and BCOi, the variant based on the improvement concept. As of the authors' knowledge, the BCOi was not used in the relevant BCO literature so far, and here it proves to be very efficient. Therefore, the development of BCOi represents major contribution of this work. To test the efficiency of our implementation we performed a set of numerical experiments on well-known benchmark problems. We compared BCOi results with the state-of-the-art heuristic algorithms. Reported results show that the BCOi is competitive with other methods with respect to both comparison criteria: solution quality and running time. Moreover, BCOi was able to generate three (out of 40) new best known solutions within negligible CPU times. The rest of this paper is organized as follows. Section 2 is devoted to the description of BCO technique, while the description of p-center problem and actual implementation of BCOi for solving it are given in Section 3. Section 4 contains experimental evaluations and Section 5 concludes the paper.

The BCO is meta-heuristic technique created by the analogy with foraging behavior of honeybees, realizing the concepts of collective intelligence. A population of artificial bees searches for the optimal solution with cooperation that enables more efficiency and allows bees to reach the goals they could not achieve individually. In this paper the BCO heuristic algorithm is used to tackle the p-center problem. Since the previously exploited constructive concept did not result in satisfactory solution qualities for benchmark examples, we developed BCOi—the improvement concept of BCO. As of the authors' knowledge our BCOi implementation is the first one exploring solution modification process instead of constructing new solutions from scratch. Therefore, the development of BCOi represent the main contribution of this work. The proposed BCOi algorithm is tested on various benchmark examples. Based on the obtained results, we can conclude that BCOi is able to produce high quality solutions within negligible CPU times. We compared BCOi performances with other techniques from relevant literature and proved that BCOi is very competitive. Comparing to state of the art techniques, BCOi generated new best known solutions for three examples (out of 40). Moreover, running times of BCOi are significantly smaller than the corresponding times required by the state-of-the-art methods. The achieved results indicate that the development of new models based on swarm intelligence principles could considerably contribute to the solution of difficult location analysis problems. There are no theoretical results at this moment that could support proposed approach. Good experimental results obtained by performed numerical evaluations represent strong motivation to try to produce some theoretical background. Beside the implementation of the BCO algorithm for other hard combinatorial problems, one of the most important aspects of future research is the mathematical justification of the BCO and BCOi technique.