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

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

An approximation algorithm for reliablefacilitylocation problem

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 transportation 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 approximation, 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 redesigned 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 approximation 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.