I摘摘 要要 有预谋的突然袭击以及恐怖袭击是对网络系统的主要危害，因此在进行设施选址的时候，应该同时考虑常规时间和紧急状态下系统的运作成本。本文将就此建立一个双层规划模型，同时文章运用了遗传算法以及禁忌搜索算法组成混合遗传算法，将此模型应用于 European150 数据集，并将其与传统模型进行对比分析，最后对一些关键参数进行了灵敏度分析。 文章首先介绍了问题来源及相关文献，然后介绍了 P 中值问题，并且列举了几个解决中值问题的常用算法。接下来介绍了设施中断问题的两个基本模型，并通过考虑在极端情况下，如何选取 P 个设施，使当有其中最主要的 R 个设施遭到破坏时的运作成本加上常规时间的运作成本最小化。我们为这个问题建立了一个双层规划模型，其中上层规划决定在哪儿建立设施,下层规划则是计算对建立的主要设施的袭击所造成的损失。我们将运用基于禁忌搜索的遗传算法来求解双层规划问题，而我们运用的禁忌搜索算法是被证明求解下层问题的最优启发式算法。我们将此模型和传统的 P 中值问题模型应用于 European150 数据集，并将结果罗列出来。由这些模型求解的几组解将被详细的列出来，通过一些分析表明，当运用不同模型所构造不同选址策略后, R个中断设施对网络系统的效率影响有多大,然后我们再进行一些关键参数的灵敏度分析，包括常规时间权重、设施数量、中断设施数量。最后我们对未来的研究方向做出一些建议。关键词关键词：设施选址 中断 双层规划 混合遗传算法 IIAbstract 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. We have cast this problem as a bi-level binary programming model ,we use hybrid genetic algorithm based and Tabu search ,we also applied it to European 150 data set, we compare the new mode with the traditional mode ,at last we discuss the sensitivity of the results. The article introduce the source of the problem firstly .Then we list several algorithms of the P-median problem. 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 Tabu search, which is proven to be the best heuristic for the lower level model by computational tests. 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 discuss the sensitivity of the results to changes in key parameters including the weight of regular condition, the number of facilities and the number of facilities interdicted. Finally, recommendations for future research are also made. Keywords: facility location interdiction bi-level programming hybrid algorithm独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 11 绪绪 论论 1.1 问题来源问题来源 高速的科技发展使得我们生活中无处不存在网络，从航空运输网络，邮政递送网络，到电力网络，电信通讯网络，互联网等等。一个网络能否正常运作取决于网络中设施能否正常运作。然而，网络中的设施以及它们所提供的服务经常会由于各种自然或者人为的灾难而受到损坏，例如地震，飓风，恐怖行为或者战争。对于这些灾难，设施的地理分布尤其显得脆弱而更易于受损，也往往会由于一两个设施的失效而导致整个系统的大面积损失。早在 1970 年，军事研究中就有人提出了相关问题。例如，在一条供给线中一座桥被炸弹炸毁了的影响有多大？如果这座桥的旁边有一条可以替代的桥，那么通过修改供给线的路径，就可以减少系统的损失。源于人们对战争中服务供给受到破坏的研究兴趣，网络系统的失效也越来越受到更多人的关注。近来，人们将焦点放在关键设施上，也就是刚才所描述的，它们的失效会对整个系统所提供的服务、供给和通信带来严重的威胁。 由于网络系统的有效运作取决于网络的连通程度，因此，网络中设施的失效会给系统运作带来不可预期的巨大损失。而当失效的是网络中的关键设施的时候，则有可能整个系统趋于崩溃状态，损失难以挽回。因此，网络中的关键设施对于维护网络的稳定性有着不可忽视的重要作用。无论是公路交通运输网络，航空网络，邮政网络还是通信网络，确定关键设施都是势在必行的举措。 从 9.11 到席卷美国邮政所的炭疽热，恐怖活动已对世界构成了巨大的威胁。近来世界范围内的恐怖活动表明设施很容易受到恐怖袭击。美国国务院于 4 月 30 日发布的 2006 年度国别恐怖活动报告称，去年全球恐怖活动较以前更为猖獗，恐怖袭击次数较 2005 年上升了 28 5， 达 14338 起； 其所造成的死亡人数比 2005年上升了 402，达 20498 人。这些数字是由美国国家反恐中心提供的。报告指出，全球恐怖事件及伤亡人数主要集中在伊拉克和阿富汗。全球去年共发生 290 起2死亡 10 人以上的大型恐怖袭击事件，其中 90发生在这两个国家。同时，非洲的恐怖活动正在呈上升趋势，从 2005 年的 253 起上升到 2006 年的 420 起。所以在进行设施选址时，我们应该高度重视恐怖主义及其可能对设施造成的巨大损失。也就是说效率和可靠性是影响设施选址问题的两大主要因素。近年来，为了抵御攻击，人们更加注意加强设施，这种攻击可能是有计划的，比如恐怖主义袭击，也可能是随机的或者说无意的，比如自然灾害。 1.2 相关研究相关研究 随机的袭击是建立在网络可靠理论的基础上的(Colbourn 1987; Shier 1991; Shooman 2002),这个理论是关于在面对随机的故障时，计算、估计、最大化网络保持贯通的概率，故障可能是中断、拥塞、封锁。Snyder and Daskin (2005)提出了许多基于经典的设施选址问题的可靠性模型，在这些模型中设施出故障的概率是给定的，它们最小化成本的同时考虑了在随机的设施故障后的期望运输成本。Berman, Krass and Menezes (2007)分析了一种设施选址模型，其中设施按照一定概率遭到中断，导致顾客在现存的设施中重新寻求服务。 中断模型在有意识的中断问题里最有效用，Brown et al. (2005)提出了一个优异的防御者/攻击者问题的指南，“中断”就是指对节点的攻击从而导致节点被破坏，或者说是降低了节点的效率，中断模型可以用来识别一个系统的薄弱环节。Wollmer (1964)是首先提出将供给线中断模型作为优化模型的人之一。Israeli, Wood (2002)研究了中断网络弧的问题，其目的是在有限的中断预算下最大化最短路径的长度，他们将这个双层、最大最小化问题建立为一个混合整数规划(MIP)，并且提出了许多有效的分解算法。这些研究与设施中断不同，它们是关于弧中断的研究。 Scaparra and Church (2004)提出了两个中断模型， 一个基于 P 中值问题， 另一个基于最大覆盖选址问题，它们都是寻求中断哪些存在的设施才能使效率或覆盖损失最大化。 Scaparra and Church (2005)将保护者/中断者问题拓展到传统的 P 中值问题，其中在网络中已经存在 P 个设施，保护者可以加强设施中的 q 个，使其免受攻击，而中断者则攻击未受到保护的设施中的 r 个，中断者的目标是最大化总的加权需求3距离，而保护者的目标是在保护设施时，最小化最差情况下的成本。上面的所有设施中断问题都假设了设施已经被选定。 Scaparra and Church