Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems
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 att...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Springer
2013
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/28287/ |
| _version_ | 1848793544129511424 |
|---|---|
| author | Qu, Rong Xu, Ying Castro-Gutierrez, Juan Landa-Silva, Dario |
| author_facet | Qu, Rong Xu, Ying Castro-Gutierrez, Juan Landa-Silva, Dario |
| author_sort | Qu, Rong |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:01:59Z |
| format | Article |
| id | nottingham-28287 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:01:59Z |
| publishDate | 2013 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-282872020-05-04T20:19:29Z https://eprints.nottingham.ac.uk/28287/ 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 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. Springer 2013-04 Article PeerReviewed Qu, Rong, Xu, Ying, Castro-Gutierrez, Juan and Landa-Silva, Dario (2013) Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. Journal of Heuristics, 19 (2). pp. 317-342. ISSN 1381-1231 delay constrained multicast routing Steiner tree problems particle swarm optimization http://link.springer.com/article/10.1007%2Fs10732-012-9198-2 doi:10.1007/s10732-012-9198-2 doi:10.1007/s10732-012-9198-2 |
| spellingShingle | delay constrained multicast routing Steiner tree problems particle swarm optimization Qu, Rong Xu, Ying Castro-Gutierrez, Juan Landa-Silva, Dario Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title_full | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title_fullStr | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title_full_unstemmed | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title_short | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems |
| title_sort | particle swarm optimization for the steiner tree in graph and delay-constrained multicast routing problems |
| topic | delay constrained multicast routing Steiner tree problems particle swarm optimization |
| url | https://eprints.nottingham.ac.uk/28287/ https://eprints.nottingham.ac.uk/28287/ https://eprints.nottingham.ac.uk/28287/ |