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

Algorithms and Analysis for the Critical Facilities Identification Problem in Network Based on P-median Model

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

Vulnerability to sudden service disruption due to deliberate sabotage and terrorist attacks is one of the major threats for network system. Much attention focuses on the need to identify critical facilities for hardening facilities against attacks. In order to identify critical facility that affected the system most after their disruptions, R-interdiction model based on P -median problem is presented. Three heuristics：greedy search, neighborhood search and Tabu search are proposed for this model. Then these heuristics are compared by three test examples： Galvao ,Europe 150 and USA 263. Computational results indicate that Tabu search consistently have the best performance. Finally we include that R -interdiction problem can increase the robustness of net- work by comparing the solutions of P -median problem and R -interdiction problem.