Bees algorithm for solving minimum routing cost spanning tree problem.

Phan Tan Quoc, Nguyen Duc Nghia
Author affiliations

Authors

  • Phan Tan Quoc Truong Dai Hoc Sai Gon
  • Nguyen Duc Nghia Truong Dai Hoc Bach Khoa Ha Noi Vien Cong nghe thong tin va Truyen thong

DOI:

https://doi.org/10.15625/1813-9663/29/3/2775

Keywords:

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

Abstract

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.

Metrics

Metrics Loading ...

Published

09-07-2013

How to Cite

[1]
P. T. Quoc and N. D. Nghia, “Bees algorithm for solving minimum routing cost spanning tree problem”., JCC, vol. 29, no. 3, pp. 265–276, Jul. 2013.

Issue

Section

Computer Science