主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2011, Vol. 19 ›› Issue (4): 120-129.

• 论文 • 上一篇    下一篇

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

杨珺, 刘舒佶, 王玲   

  1. 华中科技大学管理学院, 湖北 武汉 430074
  • 收稿日期:2009-06-11 修回日期:2011-06-28 出版日期:2011-08-30 发布日期:2011-08-30
  • 作者简介:杨珺(1976- ),女(汉族),湖北武汉人,华中科技大学管理学院副教授,研究方向:网络优化、管理决策.
  • 基金资助:

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

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

YANG Jun, LIU Shu-ji, WANG Ling   

  1. School of Management, Huazhong University of Science & Technology, Wuhan 430074, China
  • Received:2009-06-11 Revised:2011-06-28 Online:2011-08-30 Published:2011-08-30

PDF (PC)

1325

摘要： 蓄意突袭以及恐怖袭击会造成设施服务的突然中断成为网络系统的主要危害之一,因此网络设施选址决策应该同时考虑正常和紧急状态下系统的运作成本.本文研究考虑最坏中断损失下的网络设施选址问题,建立了该问题的双层规划模型,上层规划涉及设施选址决策,下层规划研究确定设施位置后,设施中断产生最大损失的问题.本文运用基于拉格朗日松弛的混合遗传算法来求解该双层规划问题.将European150数据集作为研究对象,对比研究了本文研究问题与传统的P-中位选址问题的结果,分析不同选址策略下网络系统的效率被中断影响的程度是不同的.最后通过改变一些关键参数,比如常规运作权重、设施数量、中断设施数量,对相关结果进行了分析.

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

Abstract: 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 problementails the interdictor response on which facilities to at tack.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 demonst rate 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.

Key words: facility location, interdiction, bi-level programming, hybrid algorithm

中图分类号: