考虑最坏中断损失下的P-中位设施选址问题的模型与算法研究  

A Bi-Level Programming Model and Heuristics for P-Median Location Problem with R-Interdiction Worst Loss

作　　者：杨珺[1] 刘舒佶[1] 王玲[1] 

机构地区：[1]华中科技大学管理学院,湖北武汉430074

出　　处：《中国管理科学》2011年第4期120-129,共10页Chinese Journal of Management Science

基　　金：国家自然科学基金资助项目(70601011);教育部人文社会科学研究青年基金项目(10YJC630331);华中科技大学自主创新研究基金

摘　　要：蓄意突袭以及恐怖袭击会造成设施服务的突然中断成为网络系统的主要危害之一,因此网络设施选址决策应该同时考虑正常和紧急状态下系统的运作成本。本文研究考虑最坏中断损失下的网络设施选址问题,建立了该问题的双层规划模型,上层规划涉及设施选址决策,下层规划研究确定设施位置后,设施中断产生最大损失的问题。本文运用基于拉格朗日松弛的混合遗传算法来求解该双层规划问题。将European150数据集作为研究对象,对比研究了本文研究问题与传统的P-中位选址问题的结果,分析不同选址策略下网络系统的效率被中断影响的程度是不同的。最后通过改变一些关键参数,比如常规运作权重、设施数量、中断设施数量,对相关结果进行了分析。Vulnerability to sudden service disruption due to deliberate sabotage and terrorist attacks is one of the major threats for network system.Thus,facility location strategy in network should concern the operational cost in peacetime and emergency.This article focuses on how to locate P facilities so as to minimize expected cost including the regular operational cost as well as the emergent operational cost of a worst-case attack with the interdiction of R facilities.We have cast this problem as a bi-level binary programming model where the top level problem involves the decisions about where to locate facilities and the lower level problem entails the interdictor response on which facilities to attack.We solve the bi-level problem through hybrid genetic algorithm based on lagrange relax method.Results of this problem and traditional P-median location problem applied to European 150 data set are presented.Several solutions derived from these models are presented in greater detail and demonstrate the degree to which the loss of R facilities affects network system efficiencies with different location strategy decided by these models.Then we analyze the results to changes in key parameters including the weight of regular condition,the number of facilities and the number of facilities interdicted.

关 键 词：设施选址 中断 双层规划 混合遗传算法 

分 类 号：C931[经济管理—管理学]