基于P-中位模型的網絡關鍵設施識別問題的算法設計與實現

作者：楊珺,張敏,王世偉

摘要：在網絡服務系統中，存在由于各種人為因素（恐怖行為、黑客襲擊等）導致網絡設施服務中斷的情況。為抵御有預謀的攻擊，需要更加重視如何識別網絡系統中的關鍵設施。結合P-中位選址模型，以設施失效對網絡系統運行效率影響最大化為目標，給出針對基于P-中位模型的網絡關鍵設施識別問題（即R-中斷模型），并針對該模型提出貪婪搜索、鄰域搜索和禁忌搜索3種算法。結合Galvāo、Europe150和USA263等大型的測試實例，對上述算法進行比較分析，得出禁忌搜索算法最有效的結論。最后，結合Europe150數據的例子比較了P-中位問題與R-中斷問題，認為在選址決策中事先考慮到人為攻擊導致的中斷問題可以增加網絡的抗攻擊能力，減少損失。

發文機構：華中科技大學管理學院 武漢大學信息管理學院

關鍵詞：關鍵設施識別中位問題中斷模型啟發式算法critical facilities identificationmedian probleminterdiction modelheuristic algorithm

分類號： C931[經濟管理—管理學][社會學]