Maximum flow stochastic network interdiction with uncertain restructuring: Applications to local-level drug trafficking enforcement
研究了阻断可能失败且成功后网络重构不确定的最大流随机网络阻断问题，提出两阶段随机模型并转化为单层混合整数规划求解，对毒品贩运执法有应用价值。
We study the max flow stochastic network interdiction problem with uncertain restructuring (MF-SNIP-UR). The MF-SNIP-UR, focuses on problems where interdictions may not be successful and where restructuring after successful interdictions is uncertain. We propose a two-stage stochastic model (2SSM) for this problem where the attacker makes the interdiction plan in the first stage, the network stochastically restructures based on the realization of successful interdictions, and then the defender solves a maximum flow problem in the resulting network. We formulate the 2SSM problem as a bilevel mixed integer problem (MIP) and then we convert it to a single-level MIP by using properties about restructuring and duality concepts. To solve this single-level MIP, we apply the sample average approximation (SAA) approach. We propose relaxation and heuristic methods that find a valid lower and upper bound. The heuristic method can solve problems that have at least four times the number of scenarios as the original SAA approach. We demonstrate the importance of our problem by examining applications in drug trafficking networks.