基于双层规划的反恐应急设施选址模型及算法
|
摘要
恐怖袭击常以人流密集地区的平民作为袭击目标,并存在突发性和随机性等特点,极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间,从而减轻袭击后果。首先,对反恐应急设施选址问题进行描述,并将其构造为一类离散双层规划模型。其中,上层规划是关于政府选址的0-1规划问题,下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次,结合模型和问题的特征设计算法,利用分支定界算法实现上层选址变量的隐枚举,同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后,结合南疆地区的交通拓扑网络进行算例分析,结果证明有效的选址方案可以大大降低袭击损失。
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.
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.
引文
[1]李国辉.全球恐怖袭击时空演变及风险分析研究[D].中国科学技术大学博士学位论文,2014.
[2]Lorena L,Senne E.A column generation approach to capacitated p-median problems[J].Computers&Operations Research,2004,31(6):863-876.
[3]Ceselli A,Righini G.A branch-and-price algorithm for the capacitated p-median problem[J].Networks,2005,45(3):125-142.
[4]Hakimi S L.Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J].Operations Research,1965,13(3):462-475.
[5]代文强,李仕明.欧氏平面上的占线中位选址问题分析[J].管理科学学报,2014,17(9):88-94.
[6]Batta R,Mannur N R.Covering-location models for emergency situations that require multiple response units[J].Management Science,1990,36(36):16-23.
[7]叶艳妹,张晓滨,林琼,等.基于加权集覆盖模型的农村居民点空间布局优化---以流泗镇为例[J].经济地理,2017,37(5):140-148.
[8]Cooper L.Location-allocation problems[J].Operations Research,1963,11(3):331-343.
[9]Min H,Jayaraman V,Srivastava R.Combined location-routing problems:A synthesis and future research directions[J].European Journal of Operational Research,1998,108(1):1-15.
[10]朱建明.损毁情景下应急设施选址的多目标决策方法[J].系统工程理论与实践,2015,35(3):720-727.
[11]王海军,杜丽敬,马士华.震后应急物流系统中双目标开放式选址-路径问题模型与算法研究[J].管理工程学报,2016,30(2):108-115.
[12]彭春,李金林,王珊珊.多类应急资源配置的鲁棒选址-路径优化[J].中国管理科学,2017,(6):143-150.
[13]李双琳,马祖军,郑斌,等.震后初期应急物资配送的模糊多目标选址-多式联运问题[J].中国管理科学,2013,21(2):144-151.
[14]王海军,杜丽敬,胡蝶,等.不确定条件下的应急物资配送选址-路径问题[J].系统管理学报,2015,24(6):828-834.
[15]朱佳翔,谭清美,蔡建飞,等.基于双重不确定性的应急物流配送策略[J].系统工程,2016,(3):1-8.
[16]郑斌,马祖军,周愉峰.震后应急物流动态选址-联运问题的双层规划模型[J].系统管理学报,2017,26(2):326-337.
[17]Berman O,Gavious A.Location of terror response facilities:A game between state and terrorist[J].European Journal of Operational Research,2007,177(2):1113-1133.
[18]Berman O,Gavious A,Huang R.Location of response facilities a simultaneous game between state and terrorist[J].International Journal of Operational Research,2011,10(1):102-120.
[19]韩传峰,孟令鹏,张超,等.基于完全信息动态博弈的反恐设施选址模型[J].系统工程理论与实践,2012,32(2):366-372.
[20]柴瑞瑞,孙康,陈静锋,等.连续恐怖袭击下反恐设施选址与资源调度优化模型及其应用[J].系统工程理论与实践,2016,36(2):464-472.
[21]Espejo I,Marín A,Rodriguez A M.Closest assignment constraints in discrete location problems[J].European Journal of Operational Research,2012,219(1):49-58.
[22]Hanjoul P,Peeters D.A facility location problem with clients'preference orderings[J].Regional Science&Urban Economics,1987,17(3):451-473.
[23]Scaparra M P,Church R L.A bilevel mixed-integer program for critical infrastructure protection planning[J].Computers&Operations Research,2008,35(6):1905-1923.
[24]Bard J F.Some properties of the bilevel programming problem[J].Journal of Optimization Theory and Applications,1991,68(2):371-378.
[25]Kara B Y,Verter V.Designing a Road Network for Hazardous Materials Transportation[J].Transportation Science,2004,38(2):188-196.
[26]叶一芃,张小宁.基于随机运输路径选择的物流中心选址模型[J].管理科学学报,2017,20(1):41-52.
[2]Lorena L,Senne E.A column generation approach to capacitated p-median problems[J].Computers&Operations Research,2004,31(6):863-876.
[3]Ceselli A,Righini G.A branch-and-price algorithm for the capacitated p-median problem[J].Networks,2005,45(3):125-142.
[4]Hakimi S L.Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J].Operations Research,1965,13(3):462-475.
[5]代文强,李仕明.欧氏平面上的占线中位选址问题分析[J].管理科学学报,2014,17(9):88-94.
[6]Batta R,Mannur N R.Covering-location models for emergency situations that require multiple response units[J].Management Science,1990,36(36):16-23.
[7]叶艳妹,张晓滨,林琼,等.基于加权集覆盖模型的农村居民点空间布局优化---以流泗镇为例[J].经济地理,2017,37(5):140-148.
[8]Cooper L.Location-allocation problems[J].Operations Research,1963,11(3):331-343.
[9]Min H,Jayaraman V,Srivastava R.Combined location-routing problems:A synthesis and future research directions[J].European Journal of Operational Research,1998,108(1):1-15.
[10]朱建明.损毁情景下应急设施选址的多目标决策方法[J].系统工程理论与实践,2015,35(3):720-727.
[11]王海军,杜丽敬,马士华.震后应急物流系统中双目标开放式选址-路径问题模型与算法研究[J].管理工程学报,2016,30(2):108-115.
[12]彭春,李金林,王珊珊.多类应急资源配置的鲁棒选址-路径优化[J].中国管理科学,2017,(6):143-150.
[13]李双琳,马祖军,郑斌,等.震后初期应急物资配送的模糊多目标选址-多式联运问题[J].中国管理科学,2013,21(2):144-151.
[14]王海军,杜丽敬,胡蝶,等.不确定条件下的应急物资配送选址-路径问题[J].系统管理学报,2015,24(6):828-834.
[15]朱佳翔,谭清美,蔡建飞,等.基于双重不确定性的应急物流配送策略[J].系统工程,2016,(3):1-8.
[16]郑斌,马祖军,周愉峰.震后应急物流动态选址-联运问题的双层规划模型[J].系统管理学报,2017,26(2):326-337.
[17]Berman O,Gavious A.Location of terror response facilities:A game between state and terrorist[J].European Journal of Operational Research,2007,177(2):1113-1133.
[18]Berman O,Gavious A,Huang R.Location of response facilities a simultaneous game between state and terrorist[J].International Journal of Operational Research,2011,10(1):102-120.
[19]韩传峰,孟令鹏,张超,等.基于完全信息动态博弈的反恐设施选址模型[J].系统工程理论与实践,2012,32(2):366-372.
[20]柴瑞瑞,孙康,陈静锋,等.连续恐怖袭击下反恐设施选址与资源调度优化模型及其应用[J].系统工程理论与实践,2016,36(2):464-472.
[21]Espejo I,Marín A,Rodriguez A M.Closest assignment constraints in discrete location problems[J].European Journal of Operational Research,2012,219(1):49-58.
[22]Hanjoul P,Peeters D.A facility location problem with clients'preference orderings[J].Regional Science&Urban Economics,1987,17(3):451-473.
[23]Scaparra M P,Church R L.A bilevel mixed-integer program for critical infrastructure protection planning[J].Computers&Operations Research,2008,35(6):1905-1923.
[24]Bard J F.Some properties of the bilevel programming problem[J].Journal of Optimization Theory and Applications,1991,68(2):371-378.
[25]Kara B Y,Verter V.Designing a Road Network for Hazardous Materials Transportation[J].Transportation Science,2004,38(2):188-196.
[26]叶一芃,张小宁.基于随机运输路径选择的物流中心选址模型[J].管理科学学报,2017,20(1):41-52.