Page 47 - tmp

Bee colony optimization for Hamiltonian p-Median problem

Dejan Kovač, supervisor mr Nataša Kovač

Centre for talented youth II, Belgrade, kovac.dejan.montenegro@gmail.com

Table 1. columns show the values of the cost function after
1. Introduction the run of the basic algorithm, algorithm with Improvement
I, and algorithm with both Improvement I and Improvement
This research presents a new algorithm based on II, as well as the processor time needed for obtaining the
metaheuristic algorithm with bee colony optimization, solutions. The basic algorithm was tested, and the values of
whose aim is the formation of suboptimal solutions for the cost function together with the processor time needed
Hamiltonian p-median problem. The proposed algorithm were given. After that, the basic algorithm is enriched with
has a goal to allocate the set of n vertices given in Euclidian Improvement I, which eliminates the self-intersection of
plane within k disjoint circuits in shortest processor time. Hamiltonian cycles, which leads to improvement in quality
The subsets of vertices are than used in formation of of complete solutions but increases the CPU time
Hamiltonian cycles, in such way that the cost function, insignificantly. In the end, the same set of test examples is
which in this research represents the total length of all tested on an algorithm which represents an integration of
Hamiltonian cycles, is minimized. After the implementation the basic algorithm together with the two improvements,
of basic bee colony optimization algorithm, the two where, besides the elimination of the self-intersections, the
improvement techniques are applied on the formed Improvement II is used to eliminate the intersection
complete solutions obtained by the basic algorithm. between two or more cycles.

2. Methods 4. Conclusion

During the research, a literature in which are described a Based on the preliminary solutions, it can be concluded that
mathematical formulation of Hamiltonian p-median the algorithm gives good results in generating and
problem and a detailed description of bee colony improving solutions for Hamiltonian p-median problem.
optimization algorithm was used. Algorithm and the Based on the experimental results, the proposed
formulation of the problem were coded in Wolfram implementation of the algorithm can be successfully used in
Mathematica v8.0 programming language. During the obtaining good-quality complete suboptimal solutions of
literature overview, it couldn’t be established that the other Hamiltonian p-median problem. The processor time values
authors approached this problem in a proposed way, so this are very low, and the quality of generated solutions allow
research represents a contribution in this field of research. them to be used as starting results for exact methods for
solving Hamiltonian p-median problem. Also, it is showed
that it is efficient to develop techniques for improving
3. Results complete solutions generated by bee colony optimization,
where it is necessary to develop efficient techniques who
Algorithm was tested on an example proposed in scientific will improve the solutions in minimal CPU time. In these
literature, and later on the artificially generated test test examples, the suggested techniques gave an
examples. All the tests are performed on a computer with improvement of suboptimal solutions with insignificant
the processor Pentium 4 3.00-GHz CPU with 512 MB increase in CPU time.
RAM under Microsoft Windows XP Professional Version
2002 Service Pack 2 operating system. In the first test
example, which was proposed by the authors in [4], the References
algorithm was capable of obtaining optimum for 0.01
seconds, which was an encouraging sign that the proposed [1] H. Glaab and A.Pott (2000) “The Hamiltonian p-
algorithm was well developed. The Table 1. shows some of Median Problem,” The Electronic Journal of
the results for the tests with n vertices. Combinatorics, 7, 1-25.
[2] M. Zohrehbandian (2007) “A New Formulation of the
BCO with 5 bees, k=3
n Hamiltonian p-Median Problem,” Applied Mathematical
BCO minT Impr.I minT Impr.I+II minT Sciences, 8, 355-361
33 168.529 0.076 159.125 0.078 156.620 0.156
34 155.284 0.076 152.956 0.078 150.737 0.156 [3] P. Lučić and D. Teodorović (2001) “Bee system:
35 154.383 0.092 151.626 0.093 147.943 0.171 modeling combinatorial optimization transportation
engineering problems by swarm intelligence”, Preprints of
36 168.479 0.093 154.989 0.093 152.097 0.187 the TRISTAN IV Triennial Symposium on Transportation
37 145.151 0.078 139.119 0.078 134.761 0.187 Analysis, Sao Miguel, Azores Islands, pp. 441-445
38 139.644 0.078 137.426 0.078 134.848 0.187
39 162.545 0.092 156.019 0.093 158.325 0.203 [4] M. Zohrehbandian, S. Hamidnia namini (2010) “Ant
40 182.150 0.107 179.970 0.109 179.263 0.218 colony optimization techniques for the Hamiltonian p-
median Problem”, Mathematical sciences, Vol. 4, No. 4
Table 1. Numerical results 383-390