关键词: 双层规划, 恐怖袭击, 应急设施选址, 分支定界

Abstract: Since September 11 and a series of terrorist attacks, terror has become a major threat in the world. In order to mitigate the effect of terrorist attacks, the government can pre-position enough relief resource and rescue equipments in some terror response facilities, which is helpful for improving the efficiency of emergency management.
A terror response facility location problem is considered which can be treated as a Stackelberg game between two rational decision-makers, namely, the government and the terrorist. The government is a leader, with limited budget, which first chooses some nodes in the network for building facilities, while the terrorist is a follower who chooses a node as attack target after observing the government's action. As the terrorist can always make the best response to the government, the main decision problem in this paper is how to locate some terror response facilities within a given budget such that the worst attack effect can be mitigated.
Different from current researches associate with location of terror response facility, this is the first paper that presents an integer programming model with further consideration of a budget constraint. Compared with those theoretical location models that associate with this problem, our integer model is not only more suitable for applying and designing existing combinatorial optimization algorithms, but also provides a basic model for future extensions such as stochastic and dynamic scenarios.
In this paper, a bi-level programming model is presented to characterize the interaction between the two decision-makers. The upper level problem is associated to the facility location problem of the government, and the lower level problem refers to the target choosing problem of the terrorist. All of the decision variables in both level problems are binary.
In order to solve the bi-level programming model, a hybrid algorithm is proposed for the exact solution, where a branch and bound algorithm that used in the upper level problem enumerate the location strategies implicitly, and the another quick search algorithm is designed for solving the lower level problem once a location strategy is fixed.
Our model is finally applied in a case study of 16 cities in south Xinjiang province. The numerical results show that:(i) the optimal location strategy and attack strategy under different budget are totally different, (ii) with the budget added, the government can build more facilities, and the attack effect reduces, (iii) the computing time become longer when the budget increases.

Key words: bi-level programming, terrorist attack, facility location, branch and bound