关于可靠性设施布局问题的近似算法

发布时间：2017-11-19 01:12

  本文关键词：关于可靠性设施布局问题的近似算法

  更多相关文章： 设施布局问题 可靠性 近似算法 贪心算法 原始对偶

【摘要】：设施布局问题的研究始于20世纪60年代，主要研究选择修建设施的位置和数量以及与需要得到服务的城市之间的分配关系，使得设施的修建费用和设施与城市之间的连接费用之和达到最小。设施布局问题自提出以来，，就一直占据着运筹学研究中的中心位置，在理论、算法设计和直用方面得到了广泛研究。随着实际直用的深入，设施布局问题产生了许多相直的变型和扩展。其中，具有可靠性的设施布局问题就是近年来一个热点研究问题。 在现实生活中，受自然灾害，工几罢工，恐怖袭击等因素的影响，修建的设施可能会出现故障，故连接到它的城市无法得到供直，这就直接影响到了整个系统的可靠性。针对如何以相对较小的代价换取设施布局可靠性的提升，研究几员提出了可靠性设施布局问题。现有的可靠性设施布局问题的算法基本都是基于拉格朗日松弛与连续近似方法设计的，虽然对某些实例有较好的效果，但是住住运算时间过长，而且不具有理论上好的近似度。 本文着重讨论可靠性设施布局问题的组合算法设计，主要工作如下： (1)对经典设施布局问题的各种变型和推广进行了概括总结，并系统地给出了可靠性设施布局问题的数学模型； (2)对设施布局问题现有的算法和算法设计技巧进行了归纳；分忻了现有可靠性设施布局问题的算法一一拉格朗日松弛方法和连续近似方法的缺点与不足，提出了该问题组合算法的设计思路； (3)参考经典设施布局问题的贪心算法、原始对偶算法和容错性问题中分阶段分层次处理的思想，设计了可靠性设施布局问题的一个组合算法。该算法不仅在理论上具有很好的常数近似度，而且还具有运算复杂性低的优点。这对于之前的可靠性设施布局问题只有数值实验算法，是一个很大的进步。
【学位授予单位】：中国海洋大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TB114

【共引文献】

中国期刊全文数据库 前3条

1 潘锐;朱大铭;马绍汉;;一般设施定位问题计算复杂度和近似算法研究[J];计算机研究与发展;2007年05期

2 宁钊;石胜飞;李建中;王朝坤;;传感器网络中一种支持多分辨率区域查询的数据存储方法[J];计算机研究与发展;2012年03期

3 李委霖;张鹏;朱大铭;;On Constrained Facility Location Problems[J];Journal of Computer Science & Technology;2008年05期

本文编号：1201797