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

作者：闫林成; 肖汉; 赵红娟; 孙小淇

来源：运筹学学报, 2015, 19(04): 14-24.

DOI：10.15960/j.cnki.issn.1007-6093.2015.04.002

• 设施布局问题
• 可靠性
• 近似算法
• 贪婪算法
• 原始对偶

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中,受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障,故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法,是一个很大的进步.

• 单位
  中国海洋大学