A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems |
| |
Authors: | Ying Xu Rong Qu |
| |
Affiliation: | (1) Department of Computer Engineering, Islamic Azad University, Tehran-South Branch, Tehran, Iran;(2) Department of Electrical, Computer & IT, Islamic Azad University, Qazvin Branch, Qazvin, Iran |
| |
Abstract: | This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost
(DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained
Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution
combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood
search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances
from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly
affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable
neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms
and heuristics in the literature. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|