針對多類恐怖襲擊的機場資源配置問題的松弛算法

逯婧瑜,閆喜紅,b*,郭思怡

(太原師范學院 a.數學與統計學院;b.智能優化計算與區塊鏈技術山西省重點實驗室,山西 晉中 030619)

0 引言

近年來,我國的民航事業,包括航空企業的旅客運輸量和機場建設方面,都取得了很大的進步.到2020年年底,我國國內已經頒證的民用航空機場共241個,如何保護如此龐大的國內機場網絡[1]是一項具有挑戰性的任務.

目前,國內外針對機場安全的研究有很多.比如,對機場安全風險評估中存在的問題繼續進行優化設計[2];對機場安全運行機制進行分析[3];對機場凈空障礙物進行分析測量[4];對多目標的機場停機位的預警分配模型的構建[5]等.但是針對國內機場網絡的整體安全保護的研究較少,Yan等[6]針對同一類型的恐怖分子襲擊國內機場網絡資源配置問題,建立了雙層優化模型,其中上層模型為政府向各機場提供預算分配,下層模型是恐怖分子選擇一個航班進行攻擊,從而使預期損失最大化,并采用了割平面算法來求解此雙層優化問題,同時進行了敏感性分析.

為了提高國內機場網絡安全性,在Yan等[6]的研究基礎上,考慮到實際情況中恐怖分子類型多種多樣,不同能力的恐怖分子通過機場的概率不同,從而建立針對多種類型恐怖分子的保護國內機場網絡安全的預算分配模型,并采用松弛割平面算法來求解該模型.

1 問題描述及模型建立

以下將研究如何有效地將資源分配給國內機場,以保障整個機場網絡.事先政府會確定分配給每個機場的預算數額,并估計恐怖分子成功通過各個機場的概率,從而提出一個雙層優化模型[6],其中政府是領導者,恐怖分子是追隨者.恐怖分子會通過情報獲取其成功通過率等信息,在預算有限的情況下,決定采取選用哪類方式對哪些航班段進行攻擊.恐怖分子的目標是將預期損失最大化,而政府的目標是將恐怖分子造成的最大預期損失最小化.參數設置如下表1.

表1 問題模型符號列表

下面定義決策變量:

設x,y分別是xi,yjljk對應的向量和矩陣,根據上述引入的參數和決策變量,建立如下雙層優化模型:

(1)

(2)

(3)

yjljk∈{0,1}, ?j∈J,k∈K,lj∈{1,…,nj},

(4)

在上層優化中,政府希望在預防恐怖分子襲擊事件時使得預計產生的損失W減少到最小.集合X可以保證國內所有機場獲得的政府分配的預算值總數在政府計劃限額BG之內,同時也可以保證具體到每一個機場的預算分配也在相應規定的范圍內.在下層優化中,恐怖分子也希望能通過制定最佳的攻擊方案從而將可能造成的破壞提升到最大.約束條件(2)保證了恐怖分子只能選擇一趟航班中的其中一個航班段進行攻擊.約束條件(3)保證了恐怖分子預設的攻擊成本在其合理的計劃限額BT之內的.

2 松弛割平面算法

對于上述雙層優化模型,采用松弛割平面算法.松弛割平面算法是目前針對大規模0-1整數規劃問題的一種有效求解算法[7].相比于割平面算法可以使大規模問題在很短的時間內得到一個較好的解.

該算法流程如下:

松弛割平面算法

(5)

(6)

(7)

Li≤xi≤Ui, ?i∈I.

(8)

(9)

(10)

(11)

yjljk∈[0,1], ?j∈J,k∈K,lj∈{1,…,nj}.

(12)

3 數值實驗

為了驗證所提出算法的有效性,將利用松弛割平面算法做了大量數值實驗,如下表2.所有的算法用MATLAB(R2019b)編寫.下面考慮10個機場所構成的機場網絡.取政府的總預算均為20萬元,恐怖分子的總預算為50萬元,雇傭第1類恐怖分子費用為20萬元,雇傭第2類恐怖分子類型為30萬元,其余數值隨機生成.通過將航班數從50增加到240,驗證了算法的有效性.不同規模問題的實驗結果表明,所提出的松弛割平面算法能在合理的時間內取得較為滿意的可行解.

表2 松弛割平面算法數值結果

4 小結

在文獻[6]研究基礎上,針對不同類型的恐怖分子襲擊國內機場網絡資源配置問題提出了0-1雙層整數規劃模型,并設計了松弛割平面算法.在該算法中,由于0-1整數規劃的特殊結構和性質,為此將0-1決策變量yjljk松弛到閉區間[0,1]上,為求解針對國內機場網絡安全的資源配置問題提供了新角度和新思路.