A GRASP approach for the delay-constrained multicast routing problem
A GRASP approach for the delay-constrained multicast routing problem
复制标题
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Yingchi Qu
中科院分区：
文献类型：
--
作者：
Yingchi Qu
实时多媒体应用的快速发展要求在底层计算机网络中实现基于服务质量（QoS）的组播路由。图中的约束最小Steiner树问题作为其数学模型是一个著名的NP完全问题。在本文中，我们研究了一个贪婪的随机自适应搜索过程（GRASP）的方法与VNS（可变邻域搜索）作为局部搜索策略的延迟约束最小成本（DCLC）多播路由问题。在OR库中的基准问题和一组随机生成的图上进行了大量的仿真，结果表明，本文提出的GRASP算法结合VNS在求解DCLC多播路由问题上具有很高的效率。它优于文献中的其他现有算法和算法。
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.