A GRASP approach for the delay-constrained multicast routing problem
Ying Qu · 2009
The rapid development of real-time multimedia applications requires Quality of Service (QoS) based multicast routing in underlying computer networks. The constrained minimum Steiner tree problem in graphs as the underpinning mathematical model is a well- known NP-complete problem. In this paper we investigate a GRASP (Greedy Randomized Adaptive Search Procedure) approach with VNS (Variable Neighborhood Search) as the local search strategy for the Delay-Constrained Least-Cost (DCLC) multicast routing problems. A large number of simulations carried out on the benchmark problems in the OR-library and a group of randomly generated graphs demonstrate that the proposed GRASP algorithm with VNS is highly efficient in solving the DCLC multicast routing problem. It outperforms other existing algorithms and heuristics in the literature.