Bees algorithm for solving minimum routing cost spanning tree problem.

Phan Tan Quoc, Nguyen Duc Nghia


The task to find Minimum Routing Cost Spanning Tree (MRCST) can be found in many network design problems. In general cases, the MRCST problem is proved to be NP-hard. This paper proposes an algorithm tosolve MRCST problem based on the schema of bee algorithm. The computationa lexperiment results show that our proposed algorithm outperforms the Wong's algorithm, population-basedmeta-heuristics like Max-Min Ant System (MMAS), Genetic Algorithm (GA), Artificial Bee Colony algorithm (ABC), and other  well-known heuristic algorithms. The cost to get this result is the large number of spanning trees examined by our algorithm compared to other methods, e.g., 16000 times and 1.7 times more than that of Wong's algorithm and ABC algorithm on average,  respectively.


Minimum routing cost spanning tree, bee algorithms, meta-heuristic algorithms, swarm intelligence


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology