Stochastic Maximum Flow Network Interdiction with Endogenous Uncertainty
Stochastic Maximum Flow Network Interdiction with Endogenous Uncertainty
复制标题
具有内生不确定性的随机最大流网络拦截
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Seifi
中科院分区：
文献类型：
--
作者：
S. Sadeghi;A. Seifi
描述了内生随机阻断下的两阶段最大流网络阻断问题。我们的模型由两个对手代理玩Stackelberg游戏。希望最大化某些非法商品（与毒品相同）的预期流量的走私者可以在源节点和汇节点之间传输而不被检测到。另一方面，攻击者试图通过安装一些检测器或在关键弧上添加一些安全控制来最小化走私者的目标，以增加检测的概率。大多数以前的随机网络阻断问题的文献处理外源性的不确定性，而我们认为随机程序下内生的不确定性，其中阻断者的决定可以改变的概率措施。该问题可以表述为一个双层规划，顶层攻击者在有限的预算下，选择关键弧安装检测器，并内生地提高这些弧的阻断概率。底层问题是一个两阶段的问题，解决走私者在网络中找到最大流。在第一阶段，他选择一些链接来传输流。在第二阶段，使用一个指标变量来显示他是否会在每种情况下被检测到。采用双层分解算法，通过迭代增加一些Benders割来求解该问题。采用逐次逼近的方法，处理每条路径概率测度的非线性上升，并以贩毒网络为例，识别出哪些国家对贩毒网络的阻断效果最显著。警方可以集中精力在这些地区，以减少毒品流动的数量。我们的研究结果表明，如果关键弧的选择明智和药物扩散的概率略有下降，一个显着的减少，在预期的总流量的药物可以实现。
We described the two-stage maximum flow network interdiction problem under endogenous stochastic interdiction. Our model consists of two adversary agent playing a Stackelberg game. A smuggler who wishes to maximize the expected flow of some illicit commodities (same as drugs), can be transmitted between a source node and a sink node without being detected. On the other hand, an attacker tries to minimize the objective of the smugglers by installing some detectors or adding some security controls on critical arcs to increase the probability of detection. Most previous stochastic network interdiction problems in the literature deal with exogenous uncertainty, while we consider stochastic programs under endogenous uncertainty in which the interdictor’s decisions can alter the probability measures. The problem can be formulated as a bi-level program, at the top level the attacker by a limited budget, choosing critical arcs to install detectors and enhance the interdiction probability of those arcs endogenously. The bottom level problem is a two-stage problem which is solved to find the maximum flow in the network by smugglers. In the first stage, he chooses some links to transmit the flow. In the second stage an indicator variable is used to show if he would be detected under each scenario. The bi-level decomposition algorithm has been applied to solve the problem by adding some Benders’ cuts iteratively. We applied a successive method, to deal with non-linearity rise in the probability measure of each path. A case study of drug trafficking network is applied to recognize which countries have the most significant effect in interdicting the drug trafficking network. The police can concentrate on those areas to decline the amount of drug flow. Our results demonstrate that if the critical arcs are chosen wisely and the probability of drug seizers decreases slightly, a significant decrease in the expected total flow of drugs can be achieved.
DOI：
10.1016/j.cor.2010.06.002
发表时间：
2011
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
F. Liberatore;M. P. Scaparra;Mark S. Daskin
通讯作者：
F. Liberatore;M. P. Scaparra;Mark S. Daskin