Abstract: Since September 11 and a series of terrorist attacks, terror has become a major threat in the world. In order to prevent the terrorists abroad from invading into our country and mitigate the attack risk, the government can design an effective interdiction network in the border area.
A counter-terrorism interdiction network design problem is considered which is in essence a security resources allocation problem in a fixed transportation network. This problem consists of two decision stages: the first decision stage belongs to the government who decides the optimal allocation of both "unconcealed" and "concealed" security resource in part of roads. Here the "unconcealed" resource is like security checkpoints that can be observed, while the "concealed" resource can be sensors which can't be observed directly. Both type of security resource can be used for reducing terrorist's passing probability on the fortified road. The second stage refers to the terrorist. After only observing the "unconcealed" resource, the terrorist decides the best attack target and intrusion path to maximize her perceived attack risk. Thus, the government's optimization problem is how to allocate both type of security resource in the network, such that the attack risk can be mitigate the most.
According to the decision order, above problem is addressed as a bi-level programming model. The upper level problem is associated to the resource allocation problem of the government, and the lower level problem refers to terrorist's target choosing and intrusion path optimization. In order to solve this model, a hybrid algorithm is proposed, where an improved genetic algorithm is used in the upper level problem for enumerating and updating interdict plans, and the an exact algorithm is designed for solving the lower level problem when the interdict plans are fixed.
Our model is finally applied in a case study of Kashi area. The numerical results show that: (i) the hybrid algorithm can always find good quality solutions in a very short time. (ii) As both types of resources are allocated ingenious enough, the "unconcealed" interdicts always function in the road chosen by terrorists, which greatly reduces the attack risk. (iii) the "concealed" resource is more effective in mitigating attack risk than the "unconcealed" resource.

Key words: counter-terrorism, interdiction network design, bi-level programming, improved genetic algorithm