Skip to main content

Research Repository

Advanced Search

Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

Qu, Rong; Xu, Ying; Castro-Gutierrez, Juan; Landa-Silva, Dario

Authors

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Associate Professor

Ying Xu

Juan Castro-Gutierrez



Abstract

This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.

Journal Article Type Article
Publication Date Apr 1, 2013
Journal Journal of Heuristics
Print ISSN 1381-1231
Electronic ISSN 1381-1231
Publisher Humana Press
Peer Reviewed Peer Reviewed
Volume 19
Issue 2
APA6 Citation Qu, R., Xu, Y., Castro-Gutierrez, J., & Landa-Silva, D. (2013). Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. Journal of Heuristics, 19(2), doi:10.1007/s10732-012-9198-2
DOI https://doi.org/10.1007/s10732-012-9198-2
Keywords delay constrained multicast routing, Steiner tree problems, particle swarm optimization
Publisher URL http://link.springer.com/article/10.1007%2Fs10732-012-9198-2
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information The final publication is available at Springer via http://dx.doi.org/10.1007/s10732-012-9198-2

Files

JOH12-JPSOmrp.pdf (464 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;