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

Abstract:

 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.

Key words: facility location problem, reliability, approximation algorithm, greedy method, primal dual