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

作者：杨珺,张敏,王世伟

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

发文机构：华中科技大学管理学院 武汉大学信息管理学院

关键词：关键设施识别中位问题中断模型启发式算法critical facilities identificationmedian probleminterdiction modelheuristic algorithm

分类号： C931[经济管理—管理学][社会学]