基于雙層規(guī)劃的反恐應(yīng)急設(shè)施選址模型及算法

項(xiàng) 寅

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

1 引言

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

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

因此，恐怖襲擊一旦發(fā)生，如何提高應(yīng)急救援能力并降低襲擊損失，成為了當(dāng)前反恐研究的重要課題。許多學(xué)者針對(duì)反恐應(yīng)急設(shè)施選址問(wèn)題展開(kāi)研究，并通過(guò)應(yīng)急設(shè)施的合理布局來(lái)縮短應(yīng)急人員和物資的到達(dá)時(shí)間，進(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]、多物資類(lèi)別[12-13]、隨機(jī)模糊[14-15]或動(dòng)態(tài)[16]等情形，進(jìn)而更好地?cái)M合現(xiàn)實(shí)情境。由于自然災(zāi)害的發(fā)生概率并不受選址策略的影響，因此傳統(tǒng)的應(yīng)急設(shè)施選址問(wèn)題只涉及政府一類(lèi)決策主體，因而上述模型大多被構(gòu)建為以系統(tǒng)損失最小化為目標(biāo)的單層規(guī)劃模型。相關(guān)求解算法也相對(duì)成熟，包括分支定界結(jié)合拉氏松弛的算法[3]、列生成算法[2]、各類(lèi)啟發(fā)式算法[5,10]和元啟發(fā)算法[11,13,14,16]。

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

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

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

2 模型構(gòu)建

2.1 基本分析

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

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

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

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

2.2 問(wèn)題描述

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

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

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

Loss

(1)

2.3 模型構(gòu)建

結(jié)合問(wèn)題描述中政府和恐怖分子之間的主從對(duì)策關(guān)系，將反恐應(yīng)急設(shè)施選址問(wèn)題構(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會(huì)以參數(shù)形式出現(xiàn)于下層規(guī)劃，并影響下層變量y,z的決策。當(dāng)下層規(guī)劃決策出y,z后，上層規(guī)劃的目標(biāo)函數(shù)值也就確定，并可作為上層變量x評(píng)價(jià)和更新的依據(jù)。因此，對(duì)于任意一個(gè)上層變量x，都有唯一的Loss與之對(duì)應(yīng)，并表示針對(duì)該選址策略時(shí)，恐怖分子最優(yōu)反應(yīng)下的襲擊損失。由于x是離散變量，可行解的數(shù)量是有限的，因此通過(guò)以上模型的求解必能得到一個(gè)最優(yōu)的選址策略，即x*∈argminxLoss。

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

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

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

圖2 一個(gè)簡(jiǎn)單的圖例說(shuō)明

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

(12)

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

(13)

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

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

(14)

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

(15)

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

(16)

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

證畢！

3 下層規(guī)劃求解

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

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

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

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

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

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

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

4 分支定界算法

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

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

4.1 搜索樹(shù)和搜索策略

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

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

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

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

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

4.2 上界和下界

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

4.3 分枝和剪枝

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

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

4.4 算法步驟

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

分支定界的過(guò)程為：在搜索樹(shù)中，首先判斷根結(jié)點(diǎn)處的選址策略是否滿(mǎn)足預(yù)算經(jīng)費(fèi)約束，若是，則直接得到最優(yōu)選址策略；否則，利用深度優(yōu)先、先右后左的順序進(jìn)行搜索，搜索過(guò)程用List(i)記錄上一層搜索結(jié)點(diǎn)test(i-1)所包含的兩個(gè)子結(jié)點(diǎn)，并先取右邊的子結(jié)點(diǎn)作為當(dāng)前層的搜索結(jié)點(diǎn)test(i)。若test(i)是矩陣F的子集，則繼續(xù)分支，否則將其代入下層規(guī)劃并利用算法1計(jì)算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ī)劃并計(jì)算襲擊損失,損失值賦給att_loss。算法結(jié)束,返回輸出。2. 復(fù)制test(i-1)中的所有元素到向量trans,設(shè)置trans中第i個(gè)元素值為0,并生成List(i)=test(i-1)∪trans3. while i≠0 do4. test(i)取List(i)最右端的包含非零元素的n個(gè)元素,并將List(i)的這n個(gè)元素設(shè)置為0。5. if test(i)為F的子集 then令i=i+1,繼續(xù)分支,用第2行一樣的方法生成List(i),再用第4行一樣的方法更新test(i)。6. 將test(i)對(duì)應(yīng)的選址策略代入下層規(guī)劃,用算法1求出襲擊損失值,并作為該結(jié)點(diǎn)的LB。隨后將test(i)添加至矩陣F7. if LBB then 若當(dāng)前不為葉節(jié)點(diǎn)(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é)點(diǎn)判斷，如果根結(jié)點(diǎn)處的選址方案滿(mǎn)足預(yù)算約束，停止算法并得到最優(yōu)解。第2行為生成List(i)，并用于存放test(i-1)兩個(gè)子結(jié)點(diǎn)表示的選址策略。結(jié)合圖3中的搜索樹(shù)來(lái)說(shuō)明：當(dāng)層數(shù)i=1時(shí)，test(0)=[1,1,1],trans=[0,1,1],List(1)=[1,1,1|0,1,1]表示根節(jié)點(diǎn)下兩個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的選址策略，并作為第1層需要搜索的策略。第3行-第12行為整個(gè)搜索樹(shù)的遍歷過(guò)程。其中，第4行表示搜索當(dāng)前層需要計(jì)算的新結(jié)點(diǎn)，并存入test(i)，同時(shí)更新List(i)。第5行判斷當(dāng)前搜索結(jié)點(diǎn)的選址策略是否已經(jīng)計(jì)算過(guò)，若是，繼續(xù)分支并進(jìn)入i+1層。第6行表示計(jì)算當(dāng)前搜索結(jié)點(diǎn)的下界，并保存已搜索過(guò)的策略。第7行-第8行為上下界判斷：當(dāng)LB

5 算例分析

5.1 算例描述

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

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

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

i12345678910111213141516wi4060737784651927145317527737855164229515182346ci320728470512572396370352344377400377546601560617

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

5.2 算例求解

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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

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

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