| 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. Since the problem was raised, it has always captured the central place of operation research, and has been widely studied not only in theory, but also in algorithm design and application. As the research of facility location problem goes further, more relative variations are dug. Among all the variations, the reliable facility location problem is the central issue in recent years.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 goodtheoretical approximation ratios.We mainly contribute to the algorithm design for reliable facility location problem in this paper and our jobs are as follows:a) Recapitulate all the variations of facility location problem and give a general model for reliable facility location problem;b) Summarize current algorithms for facility location problem and techniques for algorithm design; Analyses current algorithms for reliable facility location problem, which offer theory supports for latter algorithm redesign and optimization.c) Redesign 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. |
