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

An approximation algorithm for reliable facility location problem

作　　者：闫林成[1] 肖汉[2] 赵红娟[1] 孙小淇[1] 

机构地区：[1]中国海洋大学数学科学学院,山东青岛266100 [2]香港大学数学系

出　　处：《运筹学学报》2015年第4期14-24,共11页Operations Research Transactions

基　　金：国家自然科学基金(No.11271341)

摘　　要：设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中,受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障,故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法,是一个很大的进步.The research of facility location problem starts from 1960s, which mainly focuses on the locations of facilities and the assignments among cities to be connected by facilities, in order to minimize the total costs of the facility constructions and the city connections. In reality, facilities may fail from time to time due to natural disaster, labor strike, terrorist attacks or other factors. Such failures may lead to excessive trans- portation costs as cities must be served from facilities much further than their regularly assigned facilities. How to improve system reliability in relatively small costs becomes the emphasis for reliable facility location problem. However, current algorithms for reliable facility location problem are all based on Lagrangian relaxation and continuum approx- imation, which are costly in running time~ even though they may be effective for some special cases. Besides, they don＇t have good theoretical approximation ratios. We re- designed a new algorithm with constant performance ratio by referring to greedy method, primal-dual and the idea of hierarchy mentioned in the Fault Tolerant Facility Location Problems. The advantage of our new algorithm is that it will achieve a theoretical ap- proximation algorithm with numerical performance ratio if the number of assignment levels is fixed. It is a great improvement compared to the former reliable facility location problems which only have numerical experiment algorithms.

关 键 词：设施布局问题 可靠性 近似算法 贪婪算法 原始对偶 

分 类 号：O224[理学—运筹学与控制论] O157.6[理学—数学]