網(wǎng)絡(luò)阻斷問題研究熱點及發(fā)展方向

項 寅

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

0 引言

自上世紀(jì)起，網(wǎng)絡(luò)優(yōu)化問題就得到了國內(nèi)外學(xué)者的廣泛關(guān)注和深入研究[1]。傳統(tǒng)網(wǎng)絡(luò)優(yōu)化問題包括網(wǎng)絡(luò)最大流、最短路等經(jīng)典網(wǎng)絡(luò)流問題，以及衍生的指派問題、設(shè)施選址-分配問題、車輛路徑規(guī)劃問題等，往往只涉及一類決策主體，主要通過優(yōu)化固定節(jié)點之間的流量、路徑、連通性來最大化網(wǎng)絡(luò)系統(tǒng)功能，并已在各行各業(yè)中得到普遍應(yīng)用。然而，現(xiàn)實中網(wǎng)絡(luò)優(yōu)化問題的決策者往往不止一類，如交通網(wǎng)絡(luò)管制問題中的政府和承運商，邊境安檢網(wǎng)絡(luò)部署中的政府和恐怖分子等，這就使得網(wǎng)絡(luò)博弈問題的研究具備了很強的理論和現(xiàn)實意義。

網(wǎng)絡(luò)阻斷問題可視為Stackelberg博弈理論在網(wǎng)絡(luò)優(yōu)化問題中的應(yīng)用，其包含阻斷者和入侵者兩類決策人。阻斷者先行，首先阻斷網(wǎng)絡(luò)中的部分弧或節(jié)點，阻斷的作用是減少對應(yīng)的弧的流量、增加對應(yīng)弧的長度，或改變對應(yīng)節(jié)點和周圍節(jié)點的連通性。入侵者跟隨，在阻斷后的剩余網(wǎng)絡(luò)中進一步優(yōu)化節(jié)點間的最大流量、最短路徑及最優(yōu)分配方案等。根據(jù)不同決策目標(biāo)，現(xiàn)有網(wǎng)絡(luò)阻斷問題包含網(wǎng)絡(luò)最大流阻斷[2]、網(wǎng)絡(luò)最短路阻斷[3]、設(shè)施阻斷[4]和車輛路徑規(guī)劃阻斷[5]四類。與經(jīng)典網(wǎng)絡(luò)優(yōu)化問題相同，網(wǎng)絡(luò)阻斷問題的具體應(yīng)用已涉及軍事戰(zhàn)爭[6]、傳染病控制[7]、邊境安檢部署[8]、危險品運輸管控[5]，以及供應(yīng)鏈、電力、航空網(wǎng)絡(luò)中的關(guān)鍵設(shè)施保護[9～11]等問題。

在Web of Science數(shù)據(jù)庫中輸入Interdiction或Network Interdiction等關(guān)鍵詞，篩選后得到56篇文獻。但在中國知網(wǎng)上進行類似搜索后卻僅搜索到7篇相關(guān)文獻。因此，本文旨在彌補網(wǎng)絡(luò)阻斷理論在國內(nèi)研究中的空缺與不足，從模型構(gòu)建、求解算法、應(yīng)用情境和創(chuàng)新點視角進行切入并對四類基本網(wǎng)絡(luò)阻斷問題的文獻進行梳理，更對未來研究進行展望。

1 網(wǎng)絡(luò)阻斷的模型

根據(jù)入侵者(跟隨者)優(yōu)化問題的不同，網(wǎng)絡(luò)阻斷包括網(wǎng)絡(luò)最大流阻斷、最短路阻斷、設(shè)施阻斷和車輛路徑阻斷。以下對每類問題的基本模型、拓展模型歸納梳理。

1.1 網(wǎng)絡(luò)最大流阻斷模型

(1)基本模型

關(guān)于網(wǎng)絡(luò)最大流阻斷的基本模型構(gòu)建，由于版面原因。

(2)模型拓展

在基礎(chǔ)模型之上，相關(guān)研究以靜態(tài)網(wǎng)絡(luò)為起點，逐步向隨機網(wǎng)絡(luò)和動態(tài)問題拓展，并被廣泛應(yīng)用于軍事戰(zhàn)略、毒品稽查等方面。

靜態(tài)模型拓展集中在多目標(biāo)、多源多匯、多資源、不完全信息等方面。Brown等[10]考慮了網(wǎng)絡(luò)中的邊可通過分配防御資源來避免阻斷的情形，并將關(guān)于“阻斷-流量分配”的雙層規(guī)劃模型拓展為關(guān)于“防御-阻斷-流量分配”的三層規(guī)劃；Royset等[14]同時考慮了網(wǎng)絡(luò)流量、阻斷成本這兩個優(yōu)化目標(biāo)，將單目標(biāo)模型拓展成為雙目標(biāo)模型；Akguna等[17]將單一阻斷資源、單一源匯點下的網(wǎng)絡(luò)阻斷模型，拓展成為多阻斷資源、多源匯點下的阻斷模型；Sullivan等[19]構(gòu)建了歐幾里得空間中的最大流阻斷模型，并證明其為NP-難題；Jiang等[23]考慮了阻斷者對于阻斷能力存在不完全信息的情形，并構(gòu)建了不完全信息下的最大流阻斷模型。

隨機問題方面，主要考慮了阻斷能力、弧容量、阻斷策略的不確定性，并結(jié)合期望值、CaVR方法、機會約束、兩階段隨機規(guī)劃等來構(gòu)建模型。Cormican等[12]和Janjarask等[15]對基本模型拓展，考慮了阻斷能力、弧容量分別服從伯努利分布和兩點分布的情況，利用期望值法構(gòu)建效用目標(biāo)，將隨機最大流阻斷問題構(gòu)建兩階段隨機規(guī)劃模型。在此基礎(chǔ)上，Lei等[20]又考慮了不確定環(huán)境下防御者和阻斷者的風(fēng)險偏好，利用CaVR方法測度風(fēng)險并構(gòu)建雙層規(guī)劃模型；Bertsimas[20]則考慮了阻斷策略的隨機性，假設(shè)防御者僅知道各類阻斷策略的概率分布，并針對決策變量基于弧(arc-based)和路徑(path-based)的兩種情況來構(gòu)建隨機模型。

動態(tài)問題方面，Bailey等[6]考慮了阻斷策略的動態(tài)揭露特征，提出一類兩階段隨機規(guī)劃模型，其中上層規(guī)劃是關(guān)于防御者的資源分配問題，下層規(guī)劃是阻斷者關(guān)于阻斷策略的馬氏決策問題。Afshari和Kakhki[18]針對網(wǎng)絡(luò)各邊流速的差異性，提出一類動態(tài)最大流阻斷問題。為構(gòu)建模型，作者將周期T進行等分，根據(jù)各邊的流速來計算周期T內(nèi)各邊的總流量，進而將動態(tài)問題轉(zhuǎn)為類靜態(tài)問題，利用雙層規(guī)劃建模。

1.2 網(wǎng)絡(luò)最短路阻斷模型

網(wǎng)絡(luò)最短路阻斷問題同樣可視為阻斷者和入侵者間的Stackelberg博弈問題。其中，阻斷者為先行者，通過阻斷網(wǎng)絡(luò)中的邊(弧)來最小化入侵者的效用，阻斷的作用是增加對應(yīng)邊的長度，入侵者則在剩余網(wǎng)絡(luò)中決策固定起點-終點間的最短路徑。

(1)基本模型

關(guān)于網(wǎng)絡(luò)最短路阻斷的基本模型構(gòu)建，由于版面原因。

(2)模型拓展

拓展研究同樣從靜態(tài)網(wǎng)絡(luò)向隨機網(wǎng)絡(luò)和動態(tài)問題轉(zhuǎn)變。

靜態(tài)問題方面，現(xiàn)有研究多結(jié)合雙層、三層規(guī)劃理論構(gòu)建模型，并考慮了多目標(biāo)、不對稱信息等拓展情形。Bayrak等[27]和Borrero等[35]分別考慮了阻斷者和入侵者關(guān)于阻斷能力和鏈路長度的信息不對稱性，構(gòu)建雙層規(guī)劃模型并通過等價變換來使得上下層目標(biāo)函數(shù)轉(zhuǎn)為零和形式；Brown等[28]對最短路阻斷模型改進后，用來阻斷流氓國家核武器研發(fā)項目的開展，作者以最小化項目關(guān)鍵任務(wù)路徑的完成時間為目標(biāo)，加入項目技術(shù)、資源相關(guān)約束，并構(gòu)建雙層規(guī)劃模型；Claudio[29]提出一類雙目標(biāo)網(wǎng)絡(luò)最短路阻斷模型并實現(xiàn)了阻斷成本、最短路徑間的Pareto改進；Cappanera等[30]和Sadeghi等[36]均考慮了阻斷問題中網(wǎng)絡(luò)鏈路保護策略，并將“阻斷-最短路優(yōu)化”的雙層規(guī)劃模型拓展為“防御-阻斷-最短路優(yōu)化”的三層規(guī)劃模型。

隨機問題方面，主要考慮了阻斷效果、阻斷成功率、起點-終點的隨機性，同時結(jié)合期望值法，來構(gòu)建雙層規(guī)劃或兩階段隨機規(guī)劃模型。Ertem[31]考慮了阻斷成功率服從伯努利分布的情形，將隨機最短路阻斷問題構(gòu)建為兩階段隨機規(guī)劃模型；Song等[34]針對不確定的阻斷效果，設(shè)置了一系列的情景及觸發(fā)概率，采用期望值法構(gòu)建效用目標(biāo)，并構(gòu)造雙層規(guī)劃模型；Zhang等[8]考慮了阻斷效果、起點-終點的隨機性，結(jié)合期望值法，構(gòu)建雙層規(guī)劃模型。

動態(tài)問題方面，Gutin等[32]研究了動態(tài)項目關(guān)鍵路徑阻斷問題，考慮阻斷策略可根據(jù)新信息揭露進行動態(tài)調(diào)整的情形，結(jié)合最優(yōu)停時理論來將該問題構(gòu)建為一個有限期內(nèi)離散時間的馬爾科夫決策模型。Sefair等[33]和Borrero等[35]則研究了最短路阻斷中關(guān)于阻斷者和入侵者的多階段決策及序貫博弈問題，結(jié)合動態(tài)規(guī)劃理論進行建模和求解。

2.3 網(wǎng)絡(luò)設(shè)施阻斷模型

“9·11事件”后，設(shè)施阻斷問題成為網(wǎng)絡(luò)優(yōu)化中的熱點，可于評價交通、供應(yīng)鏈等網(wǎng)絡(luò)的魯棒性，并實現(xiàn)關(guān)鍵設(shè)施的識別與保護。根據(jù)是否考慮保護策略，以及襲擊后的指派原則，設(shè)施阻斷分為很多類型。若不考慮設(shè)施保護策略，則根據(jù)設(shè)施的服務(wù)指派方案，可分為RIM(r-interdiction median)和RIC(r-interdiction covering)兩類問題；若考慮設(shè)施防御策略，則RIM拓展為IMF模型(interdiction median problem with fortification)，已有研究多聚焦于IMF問題。該問題可視為防御者和襲擊者間的Stackelberg博弈問題，其決策順序為：防御者首先在有限資源下選擇若干服務(wù)設(shè)施進行防御；襲擊者觀察到防御策略后選擇未設(shè)防的設(shè)施進行襲擊；防御者最后重新優(yōu)化未受襲擊設(shè)施的服務(wù)指派問題。

(1)基本模型

關(guān)于網(wǎng)絡(luò)設(shè)施阻斷的基本模型構(gòu)建，由于版面原因。

(2)模型拓展

在IMF基本模型之上。Losada等[39]考慮了設(shè)施受襲后的恢復(fù)時間，將基本模型的0-1指派變量松弛為整數(shù)變量，使之代表服務(wù)分配的時間并添加相關(guān)約束；Hanleyab和Church[40]，以及楊珺等[41]將襲擊發(fā)生前的設(shè)施選址也作為決策變量；Ke?ici等[42]考慮了多周期內(nèi)服務(wù)設(shè)施的新增、關(guān)閉和搬遷情形，在雙層模型中添加了相關(guān)的決策變量及時空約束；Liberatore等[43]考慮了襲擊后果在網(wǎng)絡(luò)頂點間具有傳播效應(yīng)的情形，使基本模型中的ai不再是給定的參數(shù)，而變成與距離相關(guān)的分段函數(shù)；萬曉榆等[44]添加了關(guān)于設(shè)施失效概率的參數(shù)，以及防御資源和設(shè)施保護數(shù)量的上下限約束，構(gòu)建了中斷情景下的應(yīng)急設(shè)施保護選址模型；朱悅妮等[45]考慮了設(shè)施容量有限的情形，將基本模型下層的設(shè)施指派問題拓展為容量分配問題；Aliakbarian等[47]考慮了設(shè)施分層的情形，對決策變量增加了關(guān)于層級的維度，并將下層規(guī)劃拓展為分層設(shè)施服務(wù)指派問題；Medal等[49]松弛了關(guān)于傳統(tǒng)設(shè)施阻斷問題中設(shè)施保護效果為0-1變量的前提假設(shè)，將保護效果分為若干級別，并構(gòu)建兩階段隨機規(guī)劃模型；Akbari等[50]考慮了設(shè)施建造成本和客戶物資需求隨機情形下的設(shè)施阻斷問題，利用機會約束刻畫隨機變量，并將該問題構(gòu)建為一類三層規(guī)劃模型。

1.4 網(wǎng)絡(luò)車輛路徑阻斷模型

網(wǎng)絡(luò)車輛路徑阻斷將傳統(tǒng)車輛路徑問題(CVRP)拓展為主從對策問題，并主要應(yīng)用于危險品運輸管控。其中，阻斷者通過阻斷部分路段來降低風(fēng)險，阻斷意為增加對應(yīng)路段的通道費；承運商則在剩余網(wǎng)絡(luò)中通過CVRP問題優(yōu)化來降低運輸成本。

(1)基本模型

關(guān)于網(wǎng)絡(luò)設(shè)施阻斷的基本模型構(gòu)建，由于版面原因。

(2)模型拓展

網(wǎng)絡(luò)車輛路徑阻斷相關(guān)文獻歸納請參考“附錄J”。由于該問題的研究剛剛起步，相關(guān)文獻相對較少。繼文獻[5]之后，Lozano等[52]進一步考慮了路段可通過保護來免遭阻斷的情形，在基礎(chǔ)模型上添加了一層規(guī)劃問題以用來優(yōu)化防御資源的分配，并提出一類“防御-阻斷-TSP”三層模型。Bidgoli和Kheirkhah[54]則考慮了阻斷者和承運商關(guān)于路段權(quán)重信息的不對稱性，并構(gòu)建了一類新的雙層規(guī)劃模型。

2 網(wǎng)絡(luò)阻斷的算法

2.1 精確解算法

精確解算法包括：模型轉(zhuǎn)換法、Benders分解算法、分支定界算法。精確解算法在理論上可獲得最優(yōu)解，但計算時間成本較大，僅適用于中小規(guī)模問題的求解。

(1)模型轉(zhuǎn)換法(轉(zhuǎn)為單層規(guī)劃)

雙層規(guī)劃是典型NP-難題，上下層變量相互影響和作用，并增加了求解難度。模型轉(zhuǎn)換法是指結(jié)合對偶理論，來將復(fù)雜雙層模型轉(zhuǎn)為單層模型求解。以文中基本模型1為例，Wood[2]通過對下層線性規(guī)劃進行對偶變換，來將其轉(zhuǎn)為min規(guī)劃問題，再結(jié)合強對偶定理將上下層規(guī)劃進行整合為單層混合整數(shù)規(guī)劃，并利用分支定界法求解。類似地，Royset和Wood[14]將雙層規(guī)劃轉(zhuǎn)為單層規(guī)劃后，利用拉氏松弛法來減少約束后，再用分支定界法求解。在隨機雙層模型中，Lei等[22]利用抽樣平均近似方法生成隨機數(shù)，獲取期望目標(biāo)的近似值，進一步結(jié)合對偶變換轉(zhuǎn)為單層規(guī)劃求解。針對“防御-阻斷-最短路徑”的三層規(guī)劃問題，Cappanera和Scaparra[30]通過連續(xù)對偶轉(zhuǎn)換將三層規(guī)劃轉(zhuǎn)換為單層規(guī)劃，并結(jié)合分支定界法求解。

(2)Benders分解算法

Benders分解算法為割平面算法，其思路是將一個不易求解的復(fù)雜問題分解為較易的主問題和子問題，又通過主子問題的反復(fù)迭代來獲得最優(yōu)解。Israeli和Wood[3]最先使用Benders分解算法求解網(wǎng)絡(luò)最短路阻斷問題，其分別針對上下層規(guī)劃構(gòu)建主子問題，通過子問題的求解來生成和添加主問題中的Benders割，在迭代過程中，隨著Benders割的不斷生成，搜索域越來越接近最優(yōu)解，主子問題目標(biāo)值的間隔也逐漸收斂，直至獲得最優(yōu)解。Brown等[28]和Hanleyab等[40]對Benders分解算法進行改進，通過在主問題中添加了一類有效不等式(super-valid inequalities)來提高算法效率。在求解兩階段隨機規(guī)劃時，Cormican等[12]先通過蒙特卡洛方法生成隨機數(shù)，再用Benders分解算法進行求解，類似的組合方法也稱作L-shaped算法，并廣泛用于求解各類隨機網(wǎng)絡(luò)阻斷問題[6,15]。

(3)分支定界算法

分支定界法是一類隱枚舉算法，主要通過分支、剪枝策略來縮減可行解的枚舉規(guī)模。Scaparra和Church[4]最先用分支定界法求解設(shè)施阻斷問題，但其設(shè)計的分支定界算法無法直接地求解整個雙層規(guī)劃，而是通過上層變量的隱枚舉，來將雙層規(guī)劃分解為多個單層規(guī)劃求解。以文中基礎(chǔ)模型3為例，Scaparra和Church將上層規(guī)劃中表示設(shè)施防御的0-1變量z的解空間反映在二叉樹中，其中的根結(jié)點表示所有設(shè)施都未分配防御資源的情況，而各子孫結(jié)點則代表不同的防御資源分配情況。作者根據(jù)一定搜索規(guī)則來遍歷二叉樹，將當(dāng)前結(jié)點所反映的上層變量值代入下層規(guī)劃后，利用CPLEX軟件求解下層規(guī)劃，并將求得的下層目標(biāo)函數(shù)值作為當(dāng)前搜索結(jié)點的適應(yīng)值，以用作為分支、剪枝的評價依據(jù)。類似方法被廣泛應(yīng)用于求解各類設(shè)施阻斷問題[45,46]。在求解三層規(guī)劃時，Liberatore等[43]先通過下層規(guī)劃的對偶變換，將三層規(guī)劃轉(zhuǎn)為雙層規(guī)劃，再用分支定界法進行求解。

2.2 近似解算法

(1)啟發(fā)式算法

啟發(fā)式算法又稱“貪心算法”，通常利用各種優(yōu)先規(guī)則來獲取網(wǎng)絡(luò)阻斷或設(shè)施防御的相關(guān)策略。Medal等[48]在研究設(shè)施阻斷問題時設(shè)計了一類啟發(fā)式算法，即按照資源在各個設(shè)施上的“邊際效用”由大到小的順序，來制定資源的分配策略。楊珺等[38]在研究設(shè)施阻斷問題時，則根據(jù)設(shè)施的中心度大小順序來獲得阻斷策略，但通過與禁忌搜索算法對比后發(fā)現(xiàn)，啟發(fā)式算法雖然可以在較短時間得到可行解，但解的質(zhì)量卻難以保證。正因如此，現(xiàn)有文獻較少單獨采用啟發(fā)式算法，而是將啟發(fā)式算法嵌入到其他算法中并作為一個子模塊，以用來提高算法的整體效率。如Ghaffarinasab和Atayi[11]在用分支定界法求解設(shè)施阻斷問題時，就通過設(shè)計一類啟發(fā)式原則來簡化二叉樹的生成規(guī)模，其根據(jù)各個設(shè)施被襲擊的優(yōu)先級，來確定子節(jié)結(jié)點的生成對象和搜索順序。Ke?ici等[42]在設(shè)計禁忌搜索算法時，也將啟發(fā)式原則嵌入到鄰域搜索過程中，以擴大全局搜索能力。

(2)智能算法

求解雙層規(guī)劃方面，智能算法的計算邏輯與分支定界類似，通常只對上層變量進行編碼、搜索和迭代，下層規(guī)劃則通過CPLEX等優(yōu)化軟件或其他算法求解，并用作上層變量適應(yīng)度的評價依據(jù)。以求解設(shè)施阻斷問題為例，楊珺等[41]考慮了遺傳算法和拉格朗日松弛的混合算法，通過遺傳算法來實現(xiàn)上層變量的搜索、迭代和更新，而通過拉式松弛法來提高下層規(guī)劃的求解效率。Aliakbarian等[47]設(shè)計了三種算法，變鄰域算法、模擬退火算法、變鄰域-模擬退火混合算法，通過仿真實驗發(fā)現(xiàn)混合算法性能最佳。Mahmoodjanloo等[49]針對三層規(guī)劃設(shè)計了一類混合算法，上層變量通過遺傳算法實現(xiàn)搜索更新，中層規(guī)劃用一類節(jié)點枚舉算法處理，下層規(guī)劃則用CPLEX求解。對于網(wǎng)絡(luò)車輛路徑阻斷問題，Kheirkhah等[5]設(shè)計了一類協(xié)同遺傳算法，利用分而治之、合并歸總的思路提高計算效率。

2.3 算法的總體評述

(1)算法的適用模型

智能算法借助于多樣化的編碼、交叉變異、選擇方式，在求解網(wǎng)絡(luò)阻斷問題時具有廣泛適用性；而精確解算法則很容易受變量、模型結(jié)構(gòu)的影響，其適用范圍往往較局限。例如，模型轉(zhuǎn)換法通過下層對偶變換來將雙層規(guī)劃轉(zhuǎn)為單層規(guī)劃，但當(dāng)下層規(guī)劃不滿足線性規(guī)劃特征時，對偶式就很難獲??；Benders分解算法根據(jù)上、下層規(guī)劃來設(shè)計主子問題，但當(dāng)上下層問題非零和時，Benders割約束的設(shè)計難度將被增加；此外，當(dāng)決策變量為0-1變量時，分支定界算法很容易將可行解反映在二叉樹中，需要遍歷的結(jié)點數(shù)量也很有限，但當(dāng)決策變量為實數(shù)時，可行域從離散的點變?yōu)檎麄€區(qū)間，不但搜索樹較難設(shè)計，搜索效率也將降低。

(2)算法的性能

盡管網(wǎng)絡(luò)阻斷問題多為NP-難題，但智能算法可在較短時間內(nèi)求解大規(guī)模網(wǎng)絡(luò)問題，并獲得較滿意的解。Jeong[13]針對最大流阻斷模型設(shè)計遺傳算法，并將其應(yīng)用于包含685個節(jié)點和879條邊的大規(guī)模網(wǎng)絡(luò)；Ke?ici等[42]則利用禁忌搜索算法來解決了包含812個節(jié)點的設(shè)施阻斷問題，且計算時間少于1000秒。相反在精確解方面，模型轉(zhuǎn)換法對下層規(guī)劃對偶變換時，將增加一系列對偶變量，并將導(dǎo)致計算時間增加，相關(guān)研究[2,14,20]所涉及的網(wǎng)絡(luò)規(guī)模均未超過40個節(jié)點。Hanleyab和Church[40]指出在未添加有效不等式(super-valid inequalities)的前提下，Benders分解算法的計算能力非常有限，而當(dāng)其對算法改進后，可在1500秒內(nèi)計算包含70個節(jié)點的網(wǎng)絡(luò)問題。Scaparra和Church[4]為求解設(shè)施阻斷問題，設(shè)計了一類利用分支定界法隱枚舉上層變量，同時利用CPLEX求解下層規(guī)劃的混合算法，并在1500秒內(nèi)成功求解了包含150個節(jié)點的網(wǎng)絡(luò)問題，與Benders分解算法相比，計算時間成本更低。

3 網(wǎng)絡(luò)阻斷的研究展望

網(wǎng)絡(luò)阻斷問題以其重要的理論意義和應(yīng)用價值，得到了學(xué)界的廣泛關(guān)注與深入研究，由此涌現(xiàn)出豐富的數(shù)理模型和高效的求解算法。對相關(guān)文獻進行梳理后可發(fā)現(xiàn)以下局限：

第一，從網(wǎng)絡(luò)阻斷的問題類型來看，雖然目前國內(nèi)外學(xué)者已較為充分地研究了網(wǎng)絡(luò)最大流阻斷、網(wǎng)絡(luò)最短路阻斷、網(wǎng)絡(luò)設(shè)施阻斷這三類問題，開發(fā)了大量模型與算法，但關(guān)于網(wǎng)絡(luò)車輛路徑、網(wǎng)絡(luò)指派、網(wǎng)絡(luò)最小生成樹等其他類型的阻斷問題，還有待進一步的研究。

第二，從網(wǎng)絡(luò)阻斷的研究視角來看，盡管相關(guān)學(xué)者已在靜態(tài)模型的基礎(chǔ)上，對各類隨機、動態(tài)、不對稱信息視角下的阻斷模型與算法進行了拓展和完善，但仍然存在很大的拓展空間。

第三，從網(wǎng)絡(luò)阻斷的應(yīng)用范疇來看，目前網(wǎng)絡(luò)阻斷方法多應(yīng)用于交通、電力、水利網(wǎng)絡(luò)等“物理網(wǎng)絡(luò)”，而對于社會網(wǎng)絡(luò)、組織結(jié)構(gòu)網(wǎng)絡(luò)中的阻斷問題，還很少被研究。

綜上，為更好地豐富網(wǎng)絡(luò)阻斷的問題類型，拓展網(wǎng)絡(luò)阻斷的研究視角，擴大網(wǎng)絡(luò)阻斷的應(yīng)用范疇，作者就網(wǎng)絡(luò)阻斷研究提出了一些新問題、新視角、新應(yīng)用。

3.1 網(wǎng)絡(luò)阻斷的新問題

(1)網(wǎng)絡(luò)車輛路徑阻斷

目前相關(guān)研究正處在起步階段，結(jié)合經(jīng)典VRP的各類變種問題和應(yīng)用場景，未來可進一步豐富和完善這方面研究。以基礎(chǔ)模型4為例，未來還可進一步構(gòu)建包含多車場、多車型、包含軟硬時間窗、隨機、時變或多階段的決策模型，并設(shè)計有效的求解算法。

(2)網(wǎng)絡(luò)指派問題阻斷

指派問題是一類經(jīng)典網(wǎng)絡(luò)優(yōu)化問題，其往往被抽象成二分圖匹配問題，通過決策兩組節(jié)點間的匹配關(guān)系來最大化系統(tǒng)效用。未來可針對二分圖網(wǎng)絡(luò)，來研究網(wǎng)絡(luò)指派阻斷問題，可分別考慮基于“節(jié)點”和“邊”的不同阻斷策略，并加入相應(yīng)的“保護策略”，構(gòu)建關(guān)于防御者、阻斷者間的雙層或三層規(guī)劃模型與算法，以用來有效識別和保護各類指派系統(tǒng)中的關(guān)鍵性節(jié)點(如人員、設(shè)備)或邊(如通信渠道等)，并減少蓄意攻擊下的系統(tǒng)損失。

(3)網(wǎng)絡(luò)最小生成樹阻斷

在金融網(wǎng)絡(luò)風(fēng)險傳播機制的研究中，最小生成樹是一種常用的輔助方法，利用最小生成樹的唯一性可以全面而直觀地顯示系統(tǒng)性風(fēng)險的傳導(dǎo)機制[55]。因此，未來可將阻斷理論拓展到最小生成樹問題，開發(fā)網(wǎng)絡(luò)最小生成樹的阻斷模型與算法。

3.2 網(wǎng)絡(luò)阻斷的新視角

(1)資源優(yōu)化視角下的網(wǎng)絡(luò)阻斷問題

目前網(wǎng)絡(luò)阻斷問題基本上只聚焦于網(wǎng)絡(luò)關(guān)鍵邊、節(jié)點的識別問題，僅僅考慮阻斷資源在節(jié)點和邊上的0-1分配，很少對資源的分配數(shù)量，資源在網(wǎng)絡(luò)中節(jié)點間的供需指派方案進行決策。然而，以設(shè)施阻斷為例，現(xiàn)實中設(shè)施的保護或阻斷效果往往與資源的投入數(shù)量存在著線性、非線性，甚至分段線性的相關(guān)關(guān)系，而投入設(shè)施點的資源，也很可能需要從網(wǎng)絡(luò)的其他節(jié)點進行抽調(diào)。因此，未來可從資源優(yōu)化視角切入，考慮資源投入數(shù)量與阻斷效果間的各類相關(guān)關(guān)系，并優(yōu)化資源在網(wǎng)絡(luò)節(jié)點間的供需指派問題，以獲得更完整有效的阻斷策略。

(2)有限理性視角下的網(wǎng)絡(luò)阻斷問題

現(xiàn)有研究基本建立在襲擊者(或入侵者)完全理性的假設(shè)前提之上。以設(shè)施阻斷問題為例，完全理性襲擊者在面對各類防御方案時，總能計算出襲擊效用最大的節(jié)點來襲擊。然而，現(xiàn)實中的襲擊者更傾向于有限理性，其很可能選擇某一非最大效用的襲擊點，或是以某種混合策略來襲擊多個節(jié)點，并根據(jù)理性程度來決定各襲擊點的選擇概率。因此，研究有限理性行為視角下的網(wǎng)絡(luò)阻斷問題，具有較強的理論意義和實用價值。

(3)多方博弈視角下的網(wǎng)絡(luò)阻斷問題

現(xiàn)有的網(wǎng)絡(luò)阻斷問題基本上只考慮1個阻斷者和1個入侵者間的主從博弈問題。未來可以進一步研究多方博弈視角下的阻斷問題。例如，考慮1個阻斷者在面對多個相互合作或競爭的入侵者時的阻斷問題；或是多個阻斷者通過合作或競爭來阻斷1個入侵者的阻斷問題。

3.3 網(wǎng)絡(luò)阻斷的新應(yīng)用

(1)社會網(wǎng)絡(luò)中的阻斷問題

社會網(wǎng)絡(luò)分析強調(diào)利用統(tǒng)計學(xué)知識來提取網(wǎng)絡(luò)特征并對網(wǎng)絡(luò)拓撲結(jié)構(gòu)和傳播機制等進行研究。在社會網(wǎng)絡(luò)中，節(jié)點和邊的移除將影響網(wǎng)絡(luò)的特征參數(shù)和信息的傳播機制。未來可利用阻斷理論來識別社會網(wǎng)絡(luò)中的關(guān)鍵節(jié)點和邊，還可進階地考慮關(guān)于節(jié)點和邊的保護策略，并研究阻斷者和防御者間的博弈均衡。研究社會網(wǎng)絡(luò)中的阻斷問題，將可以應(yīng)用于社交網(wǎng)絡(luò)中的輿情管控，人際網(wǎng)絡(luò)中的傳染病防控等問題，進而為政府社會治理提供決策依據(jù)。

(2)組織結(jié)構(gòu)圖中的阻斷問題

目前的網(wǎng)絡(luò)阻斷研究主要聚焦在交通、電力、水利網(wǎng)絡(luò)等“物理網(wǎng)絡(luò)”上，很少涉及組織結(jié)構(gòu)圖(或網(wǎng)絡(luò))。組織結(jié)構(gòu)圖是指把企業(yè)組織分成若干部分，并且標(biāo)明各部分之間的關(guān)系結(jié)構(gòu)圖。未來可研究各式各樣組織結(jié)構(gòu)圖(如職能式、矩陣式等)中的阻斷問題，并將其應(yīng)用于阻斷和瓦解毒梟組織、傳銷組織、恐怖組織等。但與傳統(tǒng)物理網(wǎng)絡(luò)中的阻斷問題有所差別，組織結(jié)構(gòu)圖中的阻斷策略應(yīng)具有鮮明的“動態(tài)性”和“層級性”特征。以傳銷組織為例，假設(shè)其類似于樹狀的組織結(jié)構(gòu)，公安機關(guān)需要先抓獲底層的傳銷人員，才能通過審訊來獲取更上層管理人員的信息，故而阻斷只能從葉節(jié)點開始，滿足一定條件才能繼續(xù)向上推演。為此，研究類似問題需加入新的變量和約束，構(gòu)造新的模型與算法。

4 結(jié)論

網(wǎng)絡(luò)阻斷理論強調(diào)網(wǎng)絡(luò)優(yōu)化問題中的主從對策關(guān)系，通過關(guān)鍵邊或節(jié)點的識別來提高網(wǎng)絡(luò)的抗毀性?，F(xiàn)實中的網(wǎng)絡(luò)優(yōu)化決策往往涉及多個決策主體，包括軍事戰(zhàn)爭中的敵我雙方，交通管制中的政府和承運商等，使得網(wǎng)絡(luò)阻斷理論具有了很高的實用價值。本文主要從模型構(gòu)建、求解算法等方面對相關(guān)文獻進行梳理，并提出未來的潛在研究方法。通過對網(wǎng)絡(luò)阻斷研究進行綜述，可以擴大網(wǎng)絡(luò)阻斷理論在國內(nèi)的關(guān)注度，更為政府、企業(yè)等相關(guān)部門的網(wǎng)絡(luò)優(yōu)化決策提供更為有效的理論與方法支持。