基于P-中位模型的网络关键设施识别问题的算法设计与实现

被引：10

作者：

杨珺 ^{[1
]}

张敏 ^{[2
]}

王世伟 ^{[1
]}

机构：

[1] 华中科技大学管理学院

[2] 武汉大学信息管理学院

来源：

管理科学 | 2008年 / 04期

关键词：

关键设施识别; 中位问题; 中断模型; 启发式算法;

D O I：

暂无

中图分类号：

TN915.01 [通信网理论];

学科分类号：

摘要：

在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况。为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施。结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出针对基于P-中位模型的网络关键设施识别问题(即R-中断模型),并针对该模型提出贪婪搜索、邻域搜索和禁忌搜索3种算法。结合Galvo、Europe 150和USA 263等大型的测试实例,对上述算法进行比较分析,得出禁忌搜索算法最有效的结论。最后,结合Europe 150数据的例子比较了P-中位问题与R-中断问题,认为在选址决策中事先考虑到人为攻击导致的中断问题可以增加网络的抗攻击能力,减少损失。

引用

页码：46 / 53

页数：8

共 6 条

[1] 现代优化计算方法[M]. 清华大学出版社 , 邢文训,谢金星编著, 2005
[2] Algorithms for discrete and continuous multicommodity flow network interdiction problems
Lim, Churlzu
Smith, J. Cole
[J]. IIE TRANSACTIONS, 2007, 39 (01) : 15 - 26
[3] Identifying Critical Infrastructure: The Median and Covering Facility Interdiction Problems[J] . Richard L. Church,Maria P. Scaparra,Richard S. Middleton.Annals of the Association of American Geographers . 2004 (3)
[4] Tabu Search—Part II[J] . Fred Glover.ORSA Journal on Computing . 1990 (1)
[5] Tabu Search—Part I[J] . Fred Glover.ORSA Journal on Computing . 1989 (3)
[6] An Algorithmic Approach to Network Location Problems. II: The p-Medians[J] . O. Kariv,S. L. Hakimi.SIAM Journal on Applied Mathematics . 1979 (3)

← 1 →