基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标,并存在突发性和随机性等特点,极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间,从而减轻袭击后果。首先,对反恐应急设施选址问题进行描述,并将其构造为一类离散双层规划模型。其中,上层规划是关于政府选址的0-1规划问题,下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次,结合模型和问题的特征设计算法,利用分支定界算法实现上层选址变量的隐枚举,同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后,结合南疆地区的交通拓扑网络进行算例分析,结果证明有效的选址方案可以大大降低袭击损失。

A Bi-level Programming Model for Locating Terror Response Facilities

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.