网络阻断问题研究热点及发展方向

项 寅

(苏州科技大学 商学院,江苏 苏州 215009)

0 引言

自上世纪起，网络优化问题就得到了国内外学者的广泛关注和深入研究[1]。传统网络优化问题包括网络最大流、最短路等经典网络流问题，以及衍生的指派问题、设施选址-分配问题、车辆路径规划问题等，往往只涉及一类决策主体，主要通过优化固定节点之间的流量、路径、连通性来最大化网络系统功能，并已在各行各业中得到普遍应用。然而，现实中网络优化问题的决策者往往不止一类，如交通网络管制问题中的政府和承运商，边境安检网络部署中的政府和恐怖分子等，这就使得网络博弈问题的研究具备了很强的理论和现实意义。

网络阻断问题可视为Stackelberg博弈理论在网络优化问题中的应用，其包含阻断者和入侵者两类决策人。阻断者先行，首先阻断网络中的部分弧或节点，阻断的作用是减少对应的弧的流量、增加对应弧的长度，或改变对应节点和周围节点的连通性。入侵者跟随，在阻断后的剩余网络中进一步优化节点间的最大流量、最短路径及最优分配方案等。根据不同决策目标，现有网络阻断问题包含网络最大流阻断[2]、网络最短路阻断[3]、设施阻断[4]和车辆路径规划阻断[5]四类。与经典网络优化问题相同，网络阻断问题的具体应用已涉及军事战争[6]、传染病控制[7]、边境安检部署[8]、危险品运输管控[5]，以及供应链、电力、航空网络中的关键设施保护[9～11]等问题。

在Web of Science数据库中输入Interdiction或Network Interdiction等关键词，筛选后得到56篇文献。但在中国知网上进行类似搜索后却仅搜索到7篇相关文献。因此，本文旨在弥补网络阻断理论在国内研究中的空缺与不足，从模型构建、求解算法、应用情境和创新点视角进行切入并对四类基本网络阻断问题的文献进行梳理，更对未来研究进行展望。

1 网络阻断的模型

根据入侵者(跟随者)优化问题的不同，网络阻断包括网络最大流阻断、最短路阻断、设施阻断和车辆路径阻断。以下对每类问题的基本模型、拓展模型归纳梳理。

1.1 网络最大流阻断模型

(1)基本模型

关于网络最大流阻断的基本模型构建，由于版面原因。

(2)模型拓展

在基础模型之上，相关研究以静态网络为起点，逐步向随机网络和动态问题拓展，并被广泛应用于军事战略、毒品稽查等方面。

静态模型拓展集中在多目标、多源多汇、多资源、不完全信息等方面。Brown等[10]考虑了网络中的边可通过分配防御资源来避免阻断的情形，并将关于“阻断-流量分配”的双层规划模型拓展为关于“防御-阻断-流量分配”的三层规划；Royset等[14]同时考虑了网络流量、阻断成本这两个优化目标，将单目标模型拓展成为双目标模型；Akguna等[17]将单一阻断资源、单一源汇点下的网络阻断模型，拓展成为多阻断资源、多源汇点下的阻断模型；Sullivan等[19]构建了欧几里得空间中的最大流阻断模型，并证明其为NP-难题；Jiang等[23]考虑了阻断者对于阻断能力存在不完全信息的情形，并构建了不完全信息下的最大流阻断模型。

随机问题方面，主要考虑了阻断能力、弧容量、阻断策略的不确定性，并结合期望值、CaVR方法、机会约束、两阶段随机规划等来构建模型。Cormican等[12]和Janjarask等[15]对基本模型拓展，考虑了阻断能力、弧容量分别服从伯努利分布和两点分布的情况，利用期望值法构建效用目标，将随机最大流阻断问题构建两阶段随机规划模型。在此基础上，Lei等[20]又考虑了不确定环境下防御者和阻断者的风险偏好，利用CaVR方法测度风险并构建双层规划模型；Bertsimas[20]则考虑了阻断策略的随机性，假设防御者仅知道各类阻断策略的概率分布，并针对决策变量基于弧(arc-based)和路径(path-based)的两种情况来构建随机模型。

动态问题方面，Bailey等[6]考虑了阻断策略的动态揭露特征，提出一类两阶段随机规划模型，其中上层规划是关于防御者的资源分配问题，下层规划是阻断者关于阻断策略的马氏决策问题。Afshari和Kakhki[18]针对网络各边流速的差异性，提出一类动态最大流阻断问题。为构建模型，作者将周期T进行等分，根据各边的流速来计算周期T内各边的总流量，进而将动态问题转为类静态问题，利用双层规划建模。

1.2 网络最短路阻断模型

网络最短路阻断问题同样可视为阻断者和入侵者间的Stackelberg博弈问题。其中，阻断者为先行者，通过阻断网络中的边(弧)来最小化入侵者的效用，阻断的作用是增加对应边的长度，入侵者则在剩余网络中决策固定起点-终点间的最短路径。

(1)基本模型

关于网络最短路阻断的基本模型构建，由于版面原因。

(2)模型拓展

拓展研究同样从静态网络向随机网络和动态问题转变。

静态问题方面，现有研究多结合双层、三层规划理论构建模型，并考虑了多目标、不对称信息等拓展情形。Bayrak等[27]和Borrero等[35]分别考虑了阻断者和入侵者关于阻断能力和链路长度的信息不对称性，构建双层规划模型并通过等价变换来使得上下层目标函数转为零和形式；Brown等[28]对最短路阻断模型改进后，用来阻断流氓国家核武器研发项目的开展，作者以最小化项目关键任务路径的完成时间为目标，加入项目技术、资源相关约束，并构建双层规划模型；Claudio[29]提出一类双目标网络最短路阻断模型并实现了阻断成本、最短路径间的Pareto改进；Cappanera等[30]和Sadeghi等[36]均考虑了阻断问题中网络链路保护策略，并将“阻断-最短路优化”的双层规划模型拓展为“防御-阻断-最短路优化”的三层规划模型。

随机问题方面，主要考虑了阻断效果、阻断成功率、起点-终点的随机性，同时结合期望值法，来构建双层规划或两阶段随机规划模型。Ertem[31]考虑了阻断成功率服从伯努利分布的情形，将随机最短路阻断问题构建为两阶段随机规划模型；Song等[34]针对不确定的阻断效果，设置了一系列的情景及触发概率，采用期望值法构建效用目标，并构造双层规划模型；Zhang等[8]考虑了阻断效果、起点-终点的随机性，结合期望值法，构建双层规划模型。

动态问题方面，Gutin等[32]研究了动态项目关键路径阻断问题，考虑阻断策略可根据新信息揭露进行动态调整的情形，结合最优停时理论来将该问题构建为一个有限期内离散时间的马尔科夫决策模型。Sefair等[33]和Borrero等[35]则研究了最短路阻断中关于阻断者和入侵者的多阶段决策及序贯博弈问题，结合动态规划理论进行建模和求解。

2.3 网络设施阻断模型

“9·11事件”后，设施阻断问题成为网络优化中的热点，可于评价交通、供应链等网络的鲁棒性，并实现关键设施的识别与保护。根据是否考虑保护策略，以及袭击后的指派原则，设施阻断分为很多类型。若不考虑设施保护策略，则根据设施的服务指派方案，可分为RIM(r-interdiction median)和RIC(r-interdiction covering)两类问题；若考虑设施防御策略，则RIM拓展为IMF模型(interdiction median problem with fortification)，已有研究多聚焦于IMF问题。该问题可视为防御者和袭击者间的Stackelberg博弈问题，其决策顺序为：防御者首先在有限资源下选择若干服务设施进行防御；袭击者观察到防御策略后选择未设防的设施进行袭击；防御者最后重新优化未受袭击设施的服务指派问题。

(1)基本模型

关于网络设施阻断的基本模型构建，由于版面原因。

(2)模型拓展

在IMF基本模型之上。Losada等[39]考虑了设施受袭后的恢复时间，将基本模型的0-1指派变量松弛为整数变量，使之代表服务分配的时间并添加相关约束；Hanleyab和Church[40]，以及杨珺等[41]将袭击发生前的设施选址也作为决策变量；Keçici等[42]考虑了多周期内服务设施的新增、关闭和搬迁情形，在双层模型中添加了相关的决策变量及时空约束；Liberatore等[43]考虑了袭击后果在网络顶点间具有传播效应的情形，使基本模型中的ai不再是给定的参数，而变成与距离相关的分段函数；万晓榆等[44]添加了关于设施失效概率的参数，以及防御资源和设施保护数量的上下限约束，构建了中断情景下的应急设施保护选址模型；朱悦妮等[45]考虑了设施容量有限的情形，将基本模型下层的设施指派问题拓展为容量分配问题；Aliakbarian等[47]考虑了设施分层的情形，对决策变量增加了关于层级的维度，并将下层规划拓展为分层设施服务指派问题；Medal等[49]松弛了关于传统设施阻断问题中设施保护效果为0-1变量的前提假设，将保护效果分为若干级别，并构建两阶段随机规划模型；Akbari等[50]考虑了设施建造成本和客户物资需求随机情形下的设施阻断问题，利用机会约束刻画随机变量，并将该问题构建为一类三层规划模型。

1.4 网络车辆路径阻断模型

网络车辆路径阻断将传统车辆路径问题(CVRP)拓展为主从对策问题，并主要应用于危险品运输管控。其中，阻断者通过阻断部分路段来降低风险，阻断意为增加对应路段的通道费；承运商则在剩余网络中通过CVRP问题优化来降低运输成本。

(1)基本模型

关于网络设施阻断的基本模型构建，由于版面原因。

(2)模型拓展

网络车辆路径阻断相关文献归纳请参考“附录J”。由于该问题的研究刚刚起步，相关文献相对较少。继文献[5]之后，Lozano等[52]进一步考虑了路段可通过保护来免遭阻断的情形，在基础模型上添加了一层规划问题以用来优化防御资源的分配，并提出一类“防御-阻断-TSP”三层模型。Bidgoli和Kheirkhah[54]则考虑了阻断者和承运商关于路段权重信息的不对称性，并构建了一类新的双层规划模型。

2 网络阻断的算法

2.1 精确解算法

精确解算法包括：模型转换法、Benders分解算法、分支定界算法。精确解算法在理论上可获得最优解，但计算时间成本较大，仅适用于中小规模问题的求解。

(1)模型转换法(转为单层规划)

双层规划是典型NP-难题，上下层变量相互影响和作用，并增加了求解难度。模型转换法是指结合对偶理论，来将复杂双层模型转为单层模型求解。以文中基本模型1为例，Wood[2]通过对下层线性规划进行对偶变换，来将其转为min规划问题，再结合强对偶定理将上下层规划进行整合为单层混合整数规划，并利用分支定界法求解。类似地，Royset和Wood[14]将双层规划转为单层规划后，利用拉氏松弛法来减少约束后，再用分支定界法求解。在随机双层模型中，Lei等[22]利用抽样平均近似方法生成随机数，获取期望目标的近似值，进一步结合对偶变换转为单层规划求解。针对“防御-阻断-最短路径”的三层规划问题，Cappanera和Scaparra[30]通过连续对偶转换将三层规划转换为单层规划，并结合分支定界法求解。

(2)Benders分解算法

Benders分解算法为割平面算法，其思路是将一个不易求解的复杂问题分解为较易的主问题和子问题，又通过主子问题的反复迭代来获得最优解。Israeli和Wood[3]最先使用Benders分解算法求解网络最短路阻断问题，其分别针对上下层规划构建主子问题，通过子问题的求解来生成和添加主问题中的Benders割，在迭代过程中，随着Benders割的不断生成，搜索域越来越接近最优解，主子问题目标值的间隔也逐渐收敛，直至获得最优解。Brown等[28]和Hanleyab等[40]对Benders分解算法进行改进，通过在主问题中添加了一类有效不等式(super-valid inequalities)来提高算法效率。在求解两阶段随机规划时，Cormican等[12]先通过蒙特卡洛方法生成随机数，再用Benders分解算法进行求解，类似的组合方法也称作L-shaped算法，并广泛用于求解各类随机网络阻断问题[6,15]。

(3)分支定界算法

分支定界法是一类隐枚举算法，主要通过分支、剪枝策略来缩减可行解的枚举规模。Scaparra和Church[4]最先用分支定界法求解设施阻断问题，但其设计的分支定界算法无法直接地求解整个双层规划，而是通过上层变量的隐枚举，来将双层规划分解为多个单层规划求解。以文中基础模型3为例，Scaparra和Church将上层规划中表示设施防御的0-1变量z的解空间反映在二叉树中，其中的根结点表示所有设施都未分配防御资源的情况，而各子孙结点则代表不同的防御资源分配情况。作者根据一定搜索规则来遍历二叉树，将当前结点所反映的上层变量值代入下层规划后，利用CPLEX软件求解下层规划，并将求得的下层目标函数值作为当前搜索结点的适应值，以用作为分支、剪枝的评价依据。类似方法被广泛应用于求解各类设施阻断问题[45,46]。在求解三层规划时，Liberatore等[43]先通过下层规划的对偶变换，将三层规划转为双层规划，再用分支定界法进行求解。

2.2 近似解算法

(1)启发式算法

启发式算法又称“贪心算法”，通常利用各种优先规则来获取网络阻断或设施防御的相关策略。Medal等[48]在研究设施阻断问题时设计了一类启发式算法，即按照资源在各个设施上的“边际效用”由大到小的顺序，来制定资源的分配策略。杨珺等[38]在研究设施阻断问题时，则根据设施的中心度大小顺序来获得阻断策略，但通过与禁忌搜索算法对比后发现，启发式算法虽然可以在较短时间得到可行解，但解的质量却难以保证。正因如此，现有文献较少单独采用启发式算法，而是将启发式算法嵌入到其他算法中并作为一个子模块，以用来提高算法的整体效率。如Ghaffarinasab和Atayi[11]在用分支定界法求解设施阻断问题时，就通过设计一类启发式原则来简化二叉树的生成规模，其根据各个设施被袭击的优先级，来确定子节结点的生成对象和搜索顺序。Keçici等[42]在设计禁忌搜索算法时，也将启发式原则嵌入到邻域搜索过程中，以扩大全局搜索能力。

(2)智能算法

求解双层规划方面，智能算法的计算逻辑与分支定界类似，通常只对上层变量进行编码、搜索和迭代，下层规划则通过CPLEX等优化软件或其他算法求解，并用作上层变量适应度的评价依据。以求解设施阻断问题为例，杨珺等[41]考虑了遗传算法和拉格朗日松弛的混合算法，通过遗传算法来实现上层变量的搜索、迭代和更新，而通过拉式松弛法来提高下层规划的求解效率。Aliakbarian等[47]设计了三种算法，变邻域算法、模拟退火算法、变邻域-模拟退火混合算法，通过仿真实验发现混合算法性能最佳。Mahmoodjanloo等[49]针对三层规划设计了一类混合算法，上层变量通过遗传算法实现搜索更新，中层规划用一类节点枚举算法处理，下层规划则用CPLEX求解。对于网络车辆路径阻断问题，Kheirkhah等[5]设计了一类协同遗传算法，利用分而治之、合并归总的思路提高计算效率。

2.3 算法的总体评述

(1)算法的适用模型

智能算法借助于多样化的编码、交叉变异、选择方式，在求解网络阻断问题时具有广泛适用性；而精确解算法则很容易受变量、模型结构的影响，其适用范围往往较局限。例如，模型转换法通过下层对偶变换来将双层规划转为单层规划，但当下层规划不满足线性规划特征时，对偶式就很难获取；Benders分解算法根据上、下层规划来设计主子问题，但当上下层问题非零和时，Benders割约束的设计难度将被增加；此外，当决策变量为0-1变量时，分支定界算法很容易将可行解反映在二叉树中，需要遍历的结点数量也很有限，但当决策变量为实数时，可行域从离散的点变为整个区间，不但搜索树较难设计，搜索效率也将降低。

(2)算法的性能

尽管网络阻断问题多为NP-难题，但智能算法可在较短时间内求解大规模网络问题，并获得较满意的解。Jeong[13]针对最大流阻断模型设计遗传算法，并将其应用于包含685个节点和879条边的大规模网络；Keçici等[42]则利用禁忌搜索算法来解决了包含812个节点的设施阻断问题，且计算时间少于1000秒。相反在精确解方面，模型转换法对下层规划对偶变换时，将增加一系列对偶变量，并将导致计算时间增加，相关研究[2,14,20]所涉及的网络规模均未超过40个节点。Hanleyab和Church[40]指出在未添加有效不等式(super-valid inequalities)的前提下，Benders分解算法的计算能力非常有限，而当其对算法改进后，可在1500秒内计算包含70个节点的网络问题。Scaparra和Church[4]为求解设施阻断问题，设计了一类利用分支定界法隐枚举上层变量，同时利用CPLEX求解下层规划的混合算法，并在1500秒内成功求解了包含150个节点的网络问题，与Benders分解算法相比，计算时间成本更低。

3 网络阻断的研究展望

网络阻断问题以其重要的理论意义和应用价值，得到了学界的广泛关注与深入研究，由此涌现出丰富的数理模型和高效的求解算法。对相关文献进行梳理后可发现以下局限：

第一，从网络阻断的问题类型来看，虽然目前国内外学者已较为充分地研究了网络最大流阻断、网络最短路阻断、网络设施阻断这三类问题，开发了大量模型与算法，但关于网络车辆路径、网络指派、网络最小生成树等其他类型的阻断问题，还有待进一步的研究。

第二，从网络阻断的研究视角来看，尽管相关学者已在静态模型的基础上，对各类随机、动态、不对称信息视角下的阻断模型与算法进行了拓展和完善，但仍然存在很大的拓展空间。

第三，从网络阻断的应用范畴来看，目前网络阻断方法多应用于交通、电力、水利网络等“物理网络”，而对于社会网络、组织结构网络中的阻断问题，还很少被研究。

综上，为更好地丰富网络阻断的问题类型，拓展网络阻断的研究视角，扩大网络阻断的应用范畴，作者就网络阻断研究提出了一些新问题、新视角、新应用。

3.1 网络阻断的新问题

(1)网络车辆路径阻断

目前相关研究正处在起步阶段，结合经典VRP的各类变种问题和应用场景，未来可进一步丰富和完善这方面研究。以基础模型4为例，未来还可进一步构建包含多车场、多车型、包含软硬时间窗、随机、时变或多阶段的决策模型，并设计有效的求解算法。

(2)网络指派问题阻断

指派问题是一类经典网络优化问题，其往往被抽象成二分图匹配问题，通过决策两组节点间的匹配关系来最大化系统效用。未来可针对二分图网络，来研究网络指派阻断问题，可分别考虑基于“节点”和“边”的不同阻断策略，并加入相应的“保护策略”，构建关于防御者、阻断者间的双层或三层规划模型与算法，以用来有效识别和保护各类指派系统中的关键性节点(如人员、设备)或边(如通信渠道等)，并减少蓄意攻击下的系统损失。

(3)网络最小生成树阻断

在金融网络风险传播机制的研究中，最小生成树是一种常用的辅助方法，利用最小生成树的唯一性可以全面而直观地显示系统性风险的传导机制[55]。因此，未来可将阻断理论拓展到最小生成树问题，开发网络最小生成树的阻断模型与算法。

3.2 网络阻断的新视角

(1)资源优化视角下的网络阻断问题

目前网络阻断问题基本上只聚焦于网络关键边、节点的识别问题，仅仅考虑阻断资源在节点和边上的0-1分配，很少对资源的分配数量，资源在网络中节点间的供需指派方案进行决策。然而，以设施阻断为例，现实中设施的保护或阻断效果往往与资源的投入数量存在着线性、非线性，甚至分段线性的相关关系，而投入设施点的资源，也很可能需要从网络的其他节点进行抽调。因此，未来可从资源优化视角切入，考虑资源投入数量与阻断效果间的各类相关关系，并优化资源在网络节点间的供需指派问题，以获得更完整有效的阻断策略。

(2)有限理性视角下的网络阻断问题

现有研究基本建立在袭击者(或入侵者)完全理性的假设前提之上。以设施阻断问题为例，完全理性袭击者在面对各类防御方案时，总能计算出袭击效用最大的节点来袭击。然而，现实中的袭击者更倾向于有限理性，其很可能选择某一非最大效用的袭击点，或是以某种混合策略来袭击多个节点，并根据理性程度来决定各袭击点的选择概率。因此，研究有限理性行为视角下的网络阻断问题，具有较强的理论意义和实用价值。

(3)多方博弈视角下的网络阻断问题

现有的网络阻断问题基本上只考虑1个阻断者和1个入侵者间的主从博弈问题。未来可以进一步研究多方博弈视角下的阻断问题。例如，考虑1个阻断者在面对多个相互合作或竞争的入侵者时的阻断问题；或是多个阻断者通过合作或竞争来阻断1个入侵者的阻断问题。

3.3 网络阻断的新应用

(1)社会网络中的阻断问题

社会网络分析强调利用统计学知识来提取网络特征并对网络拓扑结构和传播机制等进行研究。在社会网络中，节点和边的移除将影响网络的特征参数和信息的传播机制。未来可利用阻断理论来识别社会网络中的关键节点和边，还可进阶地考虑关于节点和边的保护策略，并研究阻断者和防御者间的博弈均衡。研究社会网络中的阻断问题，将可以应用于社交网络中的舆情管控，人际网络中的传染病防控等问题，进而为政府社会治理提供决策依据。

(2)组织结构图中的阻断问题

目前的网络阻断研究主要聚焦在交通、电力、水利网络等“物理网络”上，很少涉及组织结构图(或网络)。组织结构图是指把企业组织分成若干部分，并且标明各部分之间的关系结构图。未来可研究各式各样组织结构图(如职能式、矩阵式等)中的阻断问题，并将其应用于阻断和瓦解毒枭组织、传销组织、恐怖组织等。但与传统物理网络中的阻断问题有所差别，组织结构图中的阻断策略应具有鲜明的“动态性”和“层级性”特征。以传销组织为例，假设其类似于树状的组织结构，公安机关需要先抓获底层的传销人员，才能通过审讯来获取更上层管理人员的信息，故而阻断只能从叶节点开始，满足一定条件才能继续向上推演。为此，研究类似问题需加入新的变量和约束，构造新的模型与算法。

4 结论

网络阻断理论强调网络优化问题中的主从对策关系，通过关键边或节点的识别来提高网络的抗毁性。现实中的网络优化决策往往涉及多个决策主体，包括军事战争中的敌我双方，交通管制中的政府和承运商等，使得网络阻断理论具有了很高的实用价值。本文主要从模型构建、求解算法等方面对相关文献进行梳理，并提出未来的潜在研究方法。通过对网络阻断研究进行综述，可以扩大网络阻断理论在国内的关注度，更为政府、企业等相关部门的网络优化决策提供更为有效的理论与方法支持。