項 寅

(蘇州科技大學(xué)商學(xué)院，江蘇 蘇州 215009)

1 引言

恐怖活動是指非國家的行動者為獲取一定的經(jīng)濟、政治或宗教目的，利用威脅、恐嚇或強迫等手段來實施的違法暴力事件[1]。當(dāng)前，中國面臨的恐怖主義威脅同樣嚴(yán)峻。以“東突”為首的恐怖組織在中國西部邊境地區(qū)頻頻制造恐怖活動，嚴(yán)重影響當(dāng)?shù)氐暮推健⒎€(wěn)定與發(fā)展。

特別的，恐怖活動常以人流密集地區(qū)的平民作為襲擊目標(biāo)，進(jìn)而極易導(dǎo)致嚴(yán)重的襲擊后果。例如：2001年9月11日，恐怖分子劫持民航飛機撞向世貿(mào)中心和五角大樓，導(dǎo)致2996人死亡，造成經(jīng)濟損失2000億美元；2009年7月5日，中國烏魯木齊市發(fā)生由恐怖組織策劃的打砸搶事件，導(dǎo)致197人死亡，1900人受傷，造成經(jīng)濟損失6895萬人民幣。

因此，恐怖襲擊一旦發(fā)生，如何提高應(yīng)急救援能力并降低襲擊損失，成為了當(dāng)前反恐研究的重要課題。許多學(xué)者針對反恐應(yīng)急設(shè)施選址問題展開研究，并通過應(yīng)急設(shè)施的合理布局來縮短應(yīng)急人員和物資的到達(dá)時間，進(jìn)而迅速遏制襲擊后果的惡化。

21世紀(jì)之前，應(yīng)急設(shè)施選址研究多應(yīng)用于地震、颶風(fēng)、洪水、火災(zāi)等自然災(zāi)害發(fā)生后的快速救援和有效控制，相關(guān)研究主要在靜態(tài)的p-median模型[2-3]、p-centre模型[4-5]、集覆蓋模型[6-7]、選址-分配模型[8]，以及選址-路徑模型[9]的基礎(chǔ)之上，逐步拓展到多目標(biāo)[10-11]、多物資類別[12-13]、隨機模糊[14-15]或動態(tài)[16]等情形，進(jìn)而更好地擬合現(xiàn)實情境。由于自然災(zāi)害的發(fā)生概率并不受選址策略的影響，因此傳統(tǒng)的應(yīng)急設(shè)施選址問題只涉及政府一類決策主體，因而上述模型大多被構(gòu)建為以系統(tǒng)損失最小化為目標(biāo)的單層規(guī)劃模型。相關(guān)求解算法也相對成熟，包括分支定界結(jié)合拉氏松弛的算法[3]、列生成算法[2]、各類啟發(fā)式算法[5,10]和元啟發(fā)算法[11,13,14,16]。

21世紀(jì)之后，反恐應(yīng)急設(shè)施選址成為一類新的研究問題。不同于自然災(zāi)害，恐怖分子具有理性行為人的特點，其襲擊策略會隨政府選址策略的變動而做出反應(yīng)。因此，傳統(tǒng)的p-median模型、p-centre模型、集覆蓋模型以及衍生的各類模型就不能用來反映政府和恐怖分子間的博弈和競爭關(guān)系。鑒于此，Berman等[17-18]分別考慮了選址信息公開和隱蔽這兩種情形，并利用博弈論方法將上述情形下的反恐應(yīng)急設(shè)施選址問題分別構(gòu)造為斯坦克伯格博弈選址模型和納什博弈選址模型。隨后，國內(nèi)學(xué)者韓傳峰等[19]和柴瑞瑞等[20]進(jìn)一步提出了選址信息公開時，存在生化恐怖襲擊和連續(xù)恐怖襲擊情形的斯坦克伯格博弈選址模型。

然而，上述研究存在一些不足：一方面，為方便求解，現(xiàn)有博弈選址模型的構(gòu)造思路均是通過復(fù)雜化目標(biāo)函數(shù)的方法來最大程度地減少約束條件，雖然模型的整體結(jié)構(gòu)較為簡單，但是很難在此基礎(chǔ)上應(yīng)用或改進(jìn)已有關(guān)于求解組合優(yōu)化問題的一些精確解算法，相反只能針對簡單的拓?fù)渚W(wǎng)絡(luò)進(jìn)行離散頂點的窮舉計算，或利用元啟發(fā)算法求得近似解。例如，文獻(xiàn)[18]和文獻(xiàn)[20]僅僅針對3個頂點和4個頂點組成的拓?fù)渚W(wǎng)絡(luò)進(jìn)行數(shù)值分析，而文獻(xiàn)[19]的遺傳算法又很難保證精確性。另一方面，為方便計算，現(xiàn)有研究均把設(shè)施數(shù)量作為約束條件，忽略了不同地區(qū)設(shè)施建造成本的差異性以及反恐預(yù)算經(jīng)費對于選址數(shù)量的約束。

因此，本文旨在打破上述瓶頸，考慮存在經(jīng)費預(yù)算約束的情形，將反恐應(yīng)急設(shè)施選址問題構(gòu)造為一類離散型雙層規(guī)劃模型，并設(shè)計有效的精確解算法，以期擴大現(xiàn)有反恐應(yīng)急設(shè)施選址研究所應(yīng)用的拓?fù)渚W(wǎng)絡(luò)規(guī)模，并為今后考慮隨機、動態(tài)、時變網(wǎng)絡(luò)中的反恐設(shè)施選址相關(guān)研究提供一類基礎(chǔ)的整數(shù)規(guī)劃模型。

2 模型構(gòu)建

2.1 基本分析

反恐應(yīng)急設(shè)施選址問題涉及政府和恐怖分子兩類決策主體。其中，政府是設(shè)施選址的決策者，恐怖分子則在給定的設(shè)施布局下選擇最優(yōu)的襲擊目標(biāo)。因此，反恐應(yīng)急設(shè)施選址要解決的基本問題是：給定一個離散的交通網(wǎng)絡(luò)，恐怖分子通過觀察應(yīng)急設(shè)施的位置來做出最優(yōu)反應(yīng)，并以最大化襲擊損失為目標(biāo)來選擇網(wǎng)絡(luò)中的某個頂點進(jìn)行襲擊，政府則需要在給定的預(yù)算經(jīng)費下，選擇網(wǎng)絡(luò)中的若干頂點建立應(yīng)急設(shè)施，進(jìn)而使恐怖分子最優(yōu)襲擊策略下的損失最小。

上述問題涉及兩個方面的決策問題，即政府的選址問題和恐怖分子的襲擊目標(biāo)選擇問題。其決策順序為：首先，政府在經(jīng)費約束下選擇網(wǎng)絡(luò)中的若干頂點建造應(yīng)急設(shè)施；隨后，恐怖分子觀察到設(shè)施布局后，以最大化襲擊損失為效用準(zhǔn)則，選擇網(wǎng)絡(luò)中的某一個頂點襲擊。

顯然，在決策過程中，政府的選址方案通過縮短襲擊后最近設(shè)施的救援時間來減少襲擊損失，因此設(shè)施的選址布局會影響恐怖分子襲擊頂點的選擇；相反，恐怖分子可實施的各類襲擊策略也會反過來成為政府選址時的考慮因素。因此，反恐應(yīng)急設(shè)施選址問題是一個典型的雙層規(guī)劃問題。如圖1所示，政府處于領(lǐng)導(dǎo)地位，其決策屬于上層規(guī)劃，通過設(shè)施的選位來最小化最優(yōu)襲擊策略下的最大損失；恐怖分子處于從屬地位，其決策屬于下層規(guī)劃，需結(jié)合設(shè)施的布局，選擇最優(yōu)襲擊目標(biāo)來最大化襲擊損失。

圖1 反恐應(yīng)急設(shè)施選址雙層規(guī)劃模型

2.2 問題描述

一般地，反恐應(yīng)急設(shè)施選址問題描述為：在給定的某區(qū)域交通拓?fù)渚W(wǎng)絡(luò)G(N,A)中，代表各城市的頂點集用N={i:i∈N}表示，頂點總數(shù)記為n；代表城市間公路路段的有向邊集用A={(i,j):(i,j)∈A}表示。設(shè)dij為頂點i和j間的最短路距離，并假設(shè)救援物資始終沿最短路徑運輸；設(shè)wi為頂點i發(fā)生襲擊后的救援物資需求量；設(shè)ci為頂點i處的設(shè)施建造成本。

在給定的拓?fù)渚W(wǎng)絡(luò)中，政府為先行者，首先在有限經(jīng)費B下選擇網(wǎng)絡(luò)中若干頂點建造應(yīng)急設(shè)施，在此假設(shè)每個設(shè)施的容量無限大，則政府的0-1決策變量可用xj表示，xj=1表示在頂點j建造應(yīng)急設(shè)施，否則為0；恐怖分子為跟隨者，觀察到政府選址方案后選擇某一個頂點發(fā)動襲擊，在此假設(shè)襲擊一定成功，且救援物資一定從距離襲擊點最近的設(shè)施輸出，則恐怖分子的0-1決策變量用zi表示，zi=1表示襲擊頂點i，否則為0；yij則表示襲擊發(fā)生后的救援指派方案，它在本模型中作為一類輔助決策變量，并用于救援距離表達(dá)式的構(gòu)建，yij=1表示受襲點i的需求物資由設(shè)施j提供，否則為0。因此，反恐應(yīng)急設(shè)施選址所需解決的問題是：政府對設(shè)施的選址點進(jìn)行決策，使得恐怖分子最優(yōu)襲擊策略下的損失最小。

參考文獻(xiàn)[19]，在此將襲擊損失的表達(dá)式定義為如下函數(shù)：

Loss

(1)

2.3 模型構(gòu)建

結(jié)合問題描述中政府和恐怖分子之間的主從對策關(guān)系，將反恐應(yīng)急設(shè)施選址問題構(gòu)建為如下雙層規(guī)劃模型：

(2)

(3)

xj={0,1}, ?j∈N

(4)

其中，y,z為下層規(guī)劃的解

(5)

(6)

(7)

yij≤xj, ?i∈N,j∈N

(8)

(9)

zi={0,1}, ?i∈N

(10)

yij={0,1}, ?i∈N,j∈N

(11)

模型中，式(2)-(4)是關(guān)于政府選址的上層規(guī)劃，式(5)-(11)是關(guān)于恐怖分子襲擊目標(biāo)選擇的下層規(guī)劃。上層規(guī)劃所決策的x會以參數(shù)形式出現(xiàn)于下層規(guī)劃，并影響下層變量y,z的決策。當(dāng)下層規(guī)劃決策出y,z后，上層規(guī)劃的目標(biāo)函數(shù)值也就確定，并可作為上層變量x評價和更新的依據(jù)。因此，對于任意一個上層變量x，都有唯一的Loss與之對應(yīng)，并表示針對該選址策略時，恐怖分子最優(yōu)反應(yīng)下的襲擊損失。由于x是離散變量，可行解的數(shù)量是有限的，因此通過以上模型的求解必能得到一個最優(yōu)的選址策略，即x*∈argminxLoss。

引理1. 下層規(guī)劃(5)-(11)中，約束(7)-(9)保證了在上層選址變量x參數(shù)化時，無論襲擊變量z取何值，有且僅有唯一的救援指派變量y與之對應(yīng)，且一定為已有選址點到襲擊點的最近指派方案。

證明：首先，約束(7)包含n個等式約束，由于只能襲擊一個節(jié)點，因此z確定后，僅有1個等式約束的右邊項為1，此時可行指派方案從n2個縮減為n個，均為指向襲擊節(jié)點的指派方案。其次，約束(8)包含n2個不等式約束，假設(shè)設(shè)施數(shù)為3，則約束(8)進(jìn)一步將n個可行解縮減至3個，且均表示從現(xiàn)有設(shè)施指向襲擊點的指派方案。最后，最近指派約束(9)保證了最終的指派方案一定為3個可行方案中救援距離最短的一個。因此，以上引理可得證。

以圖2為例，固定選址變量為x1=0,x2=x3=1，并計算當(dāng)襲擊變量為z1=1,z2=z3=0時，滿足約束(7)-(9)的指派方案。

圖2 一個簡單的圖例說明

結(jié)合圖2，約束(7)根據(jù)指標(biāo)i的不同取值所展開后的等式約束包括：

(12)

約束(8) 根據(jù)指標(biāo)i,j的不同取值所展開后的不等式約束包括：

(13)

約束(9) 根據(jù)指標(biāo)i,j的不同取值展開后的不等式約束包括：

當(dāng)i=1和j∈{1,2,3}時包含的約束為：

(14)

當(dāng)i=2和j∈{1,2,3}時包含的約束為：

(15)

當(dāng)i=3和j∈{1,2,3}時包含的約束為：

(16)

顯然，式(12)限定可行指派方案只能在y11,y12,y13中選擇，式(13)進(jìn)一步壓縮到y(tǒng)12,y13，式(14)則排除了y13并得到唯一指派方案y12，這顯然是設(shè)施點2,3中距離襲擊點1最近的指派。同理，一一測試x和z取其他值的情形后，仍可證明引理1的結(jié)論成立。

證畢！

3 下層規(guī)劃求解

顯然，模型(2)-(11)的上層規(guī)劃結(jié)構(gòu)簡單而下層規(guī)劃相對復(fù)雜，尤其是目標(biāo)函數(shù)(5)中的非線性乘積項ziyij，增加了下層規(guī)劃的求解難度。常規(guī)處理思路可以是增加一個新的0-1變量uij=ziyij，并通過添加約束zi+yij-uij≤1,?i,j∈N和約束zi+yij≥2uij,?i,j∈N的方法進(jìn)行線性化處理，但其缺點是增加了決策變量和約束的數(shù)量，進(jìn)而降低了計算的時間效率。

然而，由引理1可知，上層選址變量x參數(shù)化后，每給定一個襲擊變量z，就有唯一的最近指派方案y與之對應(yīng)。因此，可充分利用這一性質(zhì)，通過襲擊節(jié)點的窮舉來實現(xiàn)下層規(guī)劃的簡便計算。具體思路為：在給定選址方案x下，對n種可行的襲擊方案z進(jìn)行窮舉，依次根據(jù)約束(7)-(9)以確定每類襲擊情況下的最近救援指派方案y，隨后將指派和襲擊方案一起代入目標(biāo)函數(shù)(5)計算襲擊損失。最后選擇襲擊損失最大時所對應(yīng)的襲擊節(jié)點作為下層規(guī)劃的最優(yōu)解。相關(guān)偽代碼如下：

為方便計算，算法1中的變量z用自然數(shù)編碼，

主程序中的第3行-第5行表示將最短距離矩陣d中的元素逐行地賦給向量dis，這樣dis=[d11…d1n,d21…d2n,…,dn1…dnn]正好與y中每個元素一一對應(yīng)。第5行-第14行為每個襲擊點i

算法1. 輸入:任意兩點間的最短距離矩陣d,權(quán)重向量w,參數(shù)α,β,γ上層變量^x主程序:依次生成包含n和n2個零元素的向量U和dis2. for k = 1,2,…,n do3.矩陣d的第k行元素賦給向量dis的第(k-1)·n+1到第k?n個元素4. end for5. for i = 1,2,…,n do6. 生成包含n2個零元素的向量y7.生成包含n個元素的向量ad,其中每個元素初始賦值為無窮大8 for j = 1,2,…,n do9. if ^x的第j個元素為1 then 矩陣d的i行第j元素賦給向量ad10. end for11. 查找向量ad中各元素的最小值在矩陣dis中的位置序,并賦給h12. 零向量y中第h個位置的元素賦值為113. 計算α·dis·yT+β·ln(w(i))-γ ·w(i),并賦給U的第i個元素14. end for15. 向量U中的最大值賦給Loss,其對應(yīng)的元素序號賦給z輸出:Loss,z

的窮舉過程。其中，第5行依次枚舉的i表示襲擊節(jié)點序號，其實質(zhì)是在遍歷滿足約束(6)時的各類襲擊情形。第8行-第10行體現(xiàn)了約束(7)-(8)的作用，表示找到所有可行指派方案，并將其救援距離保存在向量ad中，這是因為第8行的for循環(huán)和第9行的邏輯判斷保證了最短距離矩陣d的第i行第j列元素就是已有選址點j到當(dāng)前襲擊點i的距離。第11行-第12行體現(xiàn)了約束(9)的作用，在可行指派方案中選擇距離最近的指派方案，并得到最優(yōu)的指派方案y。第13行表示將現(xiàn)有襲擊節(jié)點i和最優(yōu)指派方案y代入目標(biāo)函數(shù)(5)以計算襲擊損失。其中，yT為向量y的轉(zhuǎn)置，dis·yT則為最短救援距離。第15行為返回目標(biāo)函數(shù)和最優(yōu)襲擊節(jié)點。

顯然，算法1通過n次迭代就可得到最優(yōu)解，且每次迭代中的操作僅涉及四則運算、取最大值、位置查詢和賦值等簡單命令，因此其計算時間復(fù)雜度不會隨著網(wǎng)絡(luò)節(jié)點規(guī)模n的增加而呈指數(shù)函數(shù)形式增長，并可在較短時間內(nèi)實現(xiàn)下層規(guī)劃的求解。

4 分支定界算法

關(guān)于雙層規(guī)劃，Bard[24]已經(jīng)證明其為NP-難題。因其特殊的主從遞階結(jié)構(gòu)，雙層規(guī)劃的求解相對復(fù)雜。目前的求解算法多集中于下層問題為連續(xù)型規(guī)劃的形式，并通過下層規(guī)劃的對偶或KKT條件來轉(zhuǎn)化為單層規(guī)劃進(jìn)行求解[25-26]，而關(guān)于上下層均為離散規(guī)劃形式的算法研究則涉及不多。

根據(jù)本文模型(2)-(11)可發(fā)現(xiàn)：上層規(guī)劃為簡單的單資源約束離散規(guī)劃問題，當(dāng)給定上層選址變量x后，下層規(guī)劃可通過算法1快速求解，且其目標(biāo)函數(shù)Loss又正好可以反過來作為選址變量x評價和更新的依據(jù)。因此，本文設(shè)計分支定界算法以實現(xiàn)上層選址變量的隱枚舉：首先，構(gòu)造一棵搜索樹，每個結(jié)點代表一類可行的選址策略。隨后，設(shè)計相應(yīng)的搜索規(guī)則對結(jié)點進(jìn)行遍歷，當(dāng)?shù)竭_(dá)某結(jié)點后，將當(dāng)前選址策略代入下層規(guī)劃并通過算法1計算此時的襲擊損失Loss，同時結(jié)合預(yù)算約束一起作為是否剪枝的判斷依據(jù)，并通過剪枝來縮減結(jié)點的搜索規(guī)模。

4.1 搜索樹和搜索策略

結(jié)合選址問題的特性，采用設(shè)施逆向刪除的思想構(gòu)造關(guān)于選址策略x的搜索樹，首先，根結(jié)點代表所有頂點都建造應(yīng)急設(shè)施的情況，其后，從根結(jié)點開始逐層地進(jìn)行分枝，當(dāng)搜索到第i層的某個結(jié)點時，分別考慮網(wǎng)絡(luò)中頂點i的設(shè)施被刪除或被保留者這兩種情況，以此進(jìn)行分枝并得到兩個新的子結(jié)點。這樣的方法一直重復(fù)直到網(wǎng)絡(luò)中最后一個頂點的刪除或保留情形被考慮到為止。

結(jié)合圖2中的拓?fù)渚W(wǎng)絡(luò)給出搜索樹的示例，其完整的搜索樹結(jié)構(gòu)如圖3所示。其中，搜索樹的每一個結(jié)點均代表一類選址策略[x1,x2,x3]，xi=1(?i∈{1,2,3})表示在頂點i建造設(shè)施，否則為0。首先，設(shè)置根結(jié)點處的選址策略為[1,1,1]，即在每個頂點都建造設(shè)施，隨后，在搜索樹第1層中，針對頂點i=1分別考慮x1=1和x1=0兩種情況，并將根結(jié)點分為兩個子節(jié)點[1,1,1]和[0,1,1]，同理，在第2層中，繼續(xù)針對網(wǎng)絡(luò)中的頂點i=2分別考慮x2=1和x2=0兩種情況，并得到第2層的各結(jié)點[1,1,1], [1,0,1], [0,1,1], [0,0,1]，以此類推。

圖3 搜索樹構(gòu)造示意圖

顯然，上述搜索樹涵蓋了3個頂點網(wǎng)絡(luò)中所有可行的8種選址策略。但不足之處在于每個結(jié)點與其左子結(jié)點完全相同，例如第2層中的[111]與其在第三層中的左子結(jié)點[111]重復(fù)，這就使得搜索樹結(jié)點規(guī)模比可行的選址策略幾乎增加了一倍。因此，為減少不必要的重復(fù)計算，可利用深度優(yōu)先策略，按先右后左的順序依次搜索各結(jié)點。同時，構(gòu)造一個集合用于儲存已搜索過策略，并在每個新結(jié)點處判斷當(dāng)前策略是否屬于該集合，若屬于，則跳過計算并直接分支。

實踐中，為減少內(nèi)存消耗，搜索樹并非在計算前一次性構(gòu)造完畢，而是隨著結(jié)點的遍歷逐層添加和刪減選址策略，并通過“棧”來實現(xiàn)其先進(jìn)后出的特點。

4.2 上界和下界

上界UB是一個全局值，它等于已搜索過的可行選址策略中的最小襲擊損失。通常，初始上界設(shè)為無窮大，隨著遍歷的進(jìn)行，UB會不斷地動態(tài)更新，逐漸變小并越來越接近最優(yōu)值。

4.3 分枝和剪枝

在分支定界算法中，只有滿足一定前提條件時才對結(jié)點進(jìn)行分支，否則進(jìn)行剪枝。分支即進(jìn)一步遍歷該結(jié)點所包含的子節(jié)點，剪枝則進(jìn)行回溯并用于減少搜索規(guī)模。由于每個結(jié)點只有分支或剪枝兩類情形，因此僅對剪枝的條件進(jìn)行說明，若不滿足該條件，則執(zhí)行分支。

首先，當(dāng)LB≥UB時，即當(dāng)前結(jié)點的LB大于全局的UB時，需進(jìn)行剪枝。這是因為LB≥UB意味著當(dāng)前結(jié)點及其所有后繼結(jié)點所對應(yīng)的襲擊損失均已經(jīng)大于等于目前的全局最小襲擊損失，因此繼續(xù)分支并搜索后繼結(jié)點沒有意義，固而應(yīng)剪枝。

4.4 算法步驟

算法中會涉及到一些符號命名：例如i表示當(dāng)前的搜索樹層數(shù)，其作用和“指針”相同；LB和UB分別表示當(dāng)前搜索結(jié)點的下界和全局上界；向量test(i)記錄第i層的當(dāng)前搜索結(jié)點代表的選址策略，例如test(i)=[1,1,1,0]表示僅在頂點1,2,3建造設(shè)施；矩陣F記錄所有計算過的選址策略；向量opt記錄最優(yōu)的選址策略；矩陣List的作用與“?！毕嗤?，List的第i行向量記為List(i)，用于記錄當(dāng)前第i層需要計算的兩個節(jié)點，即test(i-1)的兩個子結(jié)點；tran是一個過渡向量，在生成List(i)時發(fā)揮作用。

分支定界的過程為：在搜索樹中，首先判斷根結(jié)點處的選址策略是否滿足預(yù)算經(jīng)費約束，若是，則直接得到最優(yōu)選址策略；否則，利用深度優(yōu)先、先右后左的順序進(jìn)行搜索，搜索過程用List(i)記錄上一層搜索結(jié)點test(i-1)所包含的兩個子結(jié)點，并先取右邊的子結(jié)點作為當(dāng)前層的搜索結(jié)點test(i)。若test(i)是矩陣F的子集，則繼續(xù)分支，否則將其代入下層規(guī)劃并利用算法1計算LB，若LB

分支定界算法. 輸入:距離矩陣d,權(quán)重向量w,成本向量c,預(yù)算額B,模型參數(shù)α,β,γ初始化:i=1,UB=+∞,test(0)=[1,1,…,1],list=?,opt=?,F=test(0),trans=?主程序:1. if c·test(0)T≤B then 將test(0)賦給opt,代入下層規(guī)劃并計算襲擊損失,損失值賦給att_loss。算法結(jié)束,返回輸出。2. 復(fù)制test(i-1)中的所有元素到向量trans,設(shè)置trans中第i個元素值為0,并生成List(i)=test(i-1)∪trans3. while i≠0 do4. test(i)取List(i)最右端的包含非零元素的n個元素,并將List(i)的這n個元素設(shè)置為0。5. if test(i)為F的子集 then令i=i+1,繼續(xù)分支,用第2行一樣的方法生成List(i),再用第4行一樣的方法更新test(i)。6. 將test(i)對應(yīng)的選址策略代入下層規(guī)劃,用算法1求出襲擊損失值,并作為該結(jié)點的LB。隨后將test(i)添加至矩陣F7. if LBB then 若當(dāng)前不為葉節(jié)點(i≠n),繼續(xù)分支,令i=i+1,用第2行一樣的方法生成List(i)。9. whileList(i)中各元素全為0 do10. i=i-111. if i=0 then 算法結(jié)束,將UB賦給att_loss,返回輸出。12. return to while13. return to while輸出:opt和att_loss

偽代碼中，第1行為根結(jié)點判斷，如果根結(jié)點處的選址方案滿足預(yù)算約束，停止算法并得到最優(yōu)解。第2行為生成List(i)，并用于存放test(i-1)兩個子結(jié)點表示的選址策略。結(jié)合圖3中的搜索樹來說明：當(dāng)層數(shù)i=1時，test(0)=[1,1,1],trans=[0,1,1],List(1)=[1,1,1|0,1,1]表示根節(jié)點下兩個子結(jié)點對應(yīng)的選址策略，并作為第1層需要搜索的策略。第3行-第12行為整個搜索樹的遍歷過程。其中，第4行表示搜索當(dāng)前層需要計算的新結(jié)點，并存入test(i)，同時更新List(i)。第5行判斷當(dāng)前搜索結(jié)點的選址策略是否已經(jīng)計算過，若是，繼續(xù)分支并進(jìn)入i+1層。第6行表示計算當(dāng)前搜索結(jié)點的下界，并保存已搜索過的策略。第7行-第8行為上下界判斷：當(dāng)LB

5 算例分析

5.1 算例描述

在此，以當(dāng)前恐怖襲擊最嚴(yán)重的南疆地區(qū)為例進(jìn)行算例分析。圖4a給出了南疆16個縣市的區(qū)位分布，圖4b則是將這些縣市抽象為頂點，將公路路段抽象為邊后所得到的交通拓?fù)渚W(wǎng)絡(luò)圖，共由16個節(jié)點和22條路段組成。其中，頂點i受襲擊后的物資需求wi用該地區(qū)的人口總量來近似；頂點i建造應(yīng)急設(shè)施的費用則根據(jù)新疆地區(qū)的土地成本計算而得，相關(guān)數(shù)據(jù)見表1，數(shù)據(jù)來源為《新疆統(tǒng)計年鑒2017》；此外，任意路段(i,j)的長度lij見表2，數(shù)據(jù)來源為《中國公路交通地圖冊》。

圖4 新疆喀什地區(qū)市縣分布及交通網(wǎng)絡(luò)圖

表1 各頂點i的受襲物資需求wi(件)和設(shè)施建造成本ci(萬元)

i12345678910111213141516wi4060737784651927145317527737855164229515182346ci320728470512572396370352344377400377546601560617

表2 各公路路段(i,j)的長度lij(公里)

5.2 算例求解

利用分支定界算法求解上述算例。首先定義模型中的參數(shù)α=1,β=0.5,γ=1，結(jié)合表2并利用Floyd算法計算任意兩頂點間的最短距離矩陣d，隨后依次計算不同預(yù)算經(jīng)費B下的最優(yōu)選址策略、襲擊策略、襲擊損失和計算時間。在裝有Inter Core i7 2.9GHz處理器、8GB RAM的聯(lián)想筆記本電腦上，利用Matlab2014a編譯算法，計算結(jié)果如表3所示。

結(jié)合表3中的計算結(jié)果進(jìn)行分析，進(jìn)而得到如下結(jié)論：

首先，不同預(yù)算經(jīng)費下B的最優(yōu)選址策略和襲擊策略各不相同。例如：當(dāng)B=500時，由于在所有建造費用小于500萬的節(jié)點中，節(jié)點10(巴楚)具有較大的權(quán)重，且位于北部城市密集區(qū)的中心位置，因

表3 不同預(yù)算經(jīng)費B下的最優(yōu)解和算法性能指標(biāo)

此是最佳設(shè)施建造點；此時恐怖分子則襲擊權(quán)重最大的節(jié)點4(莎車)。當(dāng)B=1000時，一個設(shè)施建在節(jié)點4(莎車)，并保護(hù)了最大權(quán)重城市，另一個設(shè)施則建在節(jié)點11(柯坪)，并與節(jié)點4產(chǎn)生協(xié)同作用，分別平衡了西南和東北地區(qū)的風(fēng)險；此時恐怖分子襲擊西北部偏遠(yuǎn)的大權(quán)重城市喀什。當(dāng)B=2000時，選址點為節(jié)點5(葉城)、節(jié)點8(岳普湖)、節(jié)點11(柯坪)，實現(xiàn)整體風(fēng)險的平衡；恐怖分子最優(yōu)襲擊點為東南部偏遠(yuǎn)的節(jié)點16(和田)。當(dāng)B=2000時，由于費用的增加，在B=2000時的基礎(chǔ)上將節(jié)點16(和田)也作為選址點；此時恐怖分子被迫襲擊東北部偏遠(yuǎn)城市阿克蘇。當(dāng)B≥2500后，選址策略總體上仍然遵從均勻分布、風(fēng)險平衡的特點，且隨著預(yù)算的增加，其建造節(jié)點的權(quán)重也逐漸增加。

其次，隨著預(yù)算費用的增加，設(shè)施數(shù)量不斷增加，相應(yīng)的襲擊損失不斷減少，但是襲擊損失的減少程度不斷減低，說明兩者間存在“邊際效用遞減”規(guī)律。因此，政府可通過增加反恐預(yù)算經(jīng)費的方法來規(guī)避襲擊風(fēng)險，但需對經(jīng)費的投入進(jìn)行合理決策。

最后，隨著預(yù)算費用的增加，計算時間不斷減少。這是由于通過設(shè)施逆向刪減法所構(gòu)造的搜索樹的特殊結(jié)構(gòu)而造成的：預(yù)算非常小時，設(shè)施數(shù)量很少，因此往往需要搜索到葉節(jié)點才能找到可行解并更新上界，剪枝發(fā)生在搜索樹下部的幾率較大，剪枝規(guī)模相對較??；相反，預(yù)算較高時，設(shè)施數(shù)量較多，剪枝發(fā)生在搜索樹上部的機會就相對更大，剪枝規(guī)模更大。

6 結(jié)語

當(dāng)前，恐怖主義威脅日趨嚴(yán)峻。為提高恐怖襲擊應(yīng)急救援能力，本文針對反恐應(yīng)急設(shè)施選址布局問題展開研究，根據(jù)政府和恐怖分子間的主從對策關(guān)系構(gòu)造雙層規(guī)劃模型，針對模型特點設(shè)計分支定界算法，并結(jié)合南疆地區(qū)的交通網(wǎng)絡(luò)進(jìn)行實例分析。

在實例分析中，本文不僅計算和獲取了各決策情境下的應(yīng)急設(shè)施最優(yōu)選址布局方案，并為政府反恐科學(xué)決策提供支持；還通過各情境的對比而發(fā)現(xiàn)了反恐經(jīng)費和襲擊損失之間的“邊際效用遞減規(guī)律”，進(jìn)而建議政府對反恐經(jīng)費進(jìn)行合理預(yù)算，以避免資源浪費現(xiàn)象或防御盲點的出現(xiàn)。

為簡化模型和便于求解，本文模型仍存在一些局限。第一，本模型假設(shè)恐怖分子具有強大的計算能力并可針對設(shè)施布局做出最優(yōu)反應(yīng)，因此較適用于恐怖分子理性程度較高的情形。第二，結(jié)合我國政府在西部反恐中的大量人力與物資投入，本模型提出了應(yīng)急設(shè)施存儲物資容量充足的前提假設(shè)，而該假設(shè)卻與一些中東及北非貧窮國家的物資匱乏情況相違背，進(jìn)而限制了其在全球范圍應(yīng)用的普適性。第三，由于襲擊后果較難度量，本模型僅僅結(jié)合城市人口數(shù)量進(jìn)行近似，且忽略了現(xiàn)實中襲擊效果的隨機性和不確定性，固而會對模型的應(yīng)用效果產(chǎn)生一定影響。

因此，未來研究可致力于突破上述局限，在本文所提出的基礎(chǔ)模型之上拓展改進(jìn)，進(jìn)一步考慮恐怖分子為“有限理性”，應(yīng)急設(shè)施容量有限，或襲擊后果存在隨機或不確定性的情形。