Abstract: With the implementation of the Belt and Road strategy, the cooperation between our country and neighbors are becoming more and more frequent, which also increases the possibility of terrorists’invasion. Thus, in order to prevent terrorists’ invasion, this paper takes terrorists’ computing powerinto account, and considers a new network interdiction problem which is in essence a security resources allocation problem in a fixed transportation network.First, we address this problem as a bi-level programming model, where the upper-level problem is associated to the government’s network design problem, and the lower-level problem belongs to the terrorists, who decide the best target and invasion routes. Second, we propose a hybridalgorithm in whichthe Tabu search is used in the upper-level problem for enumerating and updating interdict plans, and an exact algorithm is designed for solving the lower level problem when the interdict plans are fixed. Third, we apply this model to a real-world case study and present a simulation analysis. The conclusion includes: (i)The stronger the terrorist’s computing power is, the more attack risk it causes, (ii)the government’s best interdict action is affected by terrorists’ computing power, but still has some principle in common. (iii)When the resource of interdiction increases, the marginal risk decreases obviously.

Key words: terrorist, security inspection resources, interdiction network, bi-level programming, Tabu search

摘要： “一带一路”战略加深了我国与邻国的合作交流,也为境外恐怖分子的潜入提供可乘之机。为防止恐怖分子潜入,提出一类新的恐怖分子入侵阻止网络设计问题,充分考虑恐怖分子的计算能力,通过决策有限安检资源在边境交通网络中的最优分配来降低袭击风险。首先,将该问题构造为双层规划模型,上层规划是政府的阻止网络设计问题,下层规划是恐怖分子的袭击节点选择和入侵路径优化问题;其次,设计一类用禁忌搜索处理上层规划,并结合下层规划直接求解的混合算法;最后,结合南疆实例进行仿真分析,结果发现:恐怖分子计算能力越强,网络城市节点受袭风险越大;政府最优阻断方案随恐怖分子计算能力强弱变化而变化,但存在一定共性原则;增加阻断资源投入可降低袭击风险,但两者存在“边际效用递减”关系。

关键词: 恐怖分子, 安检资源, 网络设计, 双层规划, 禁忌搜索