Toward Balancing the Efficiency and Effectiveness in k-Facility Relocation Problem

Facility Relocation (FR), which is an effort to reallocate the placement of facilities to adapt to the changes of urban planning, has remarkable impact on many areas. Existing solutions fail to guarantee the result quality on relocating k > 1 facilities. As k-FR problem is NP-complete and is not submodular or non-decreasing, traditional greedy algorithm cannot be directly applied. We propose to transform k-FR into another facility placement problem, which is submodular and non-decreasing. We prove that the optimal solutions of both problems are equivalent. Accordingly, we present the first approximate solution toward the k-FR, FR2FP. Our extensive comparison over both FR2FP and the state-of-the-art solution shows that FR2FP, although it provides approximation guarantee, cannot necessarily given superior results. The comparison motivates us to present an advanced approximate solution, FR2FP-ex. Moreover, based on Lagrangian relaxation, we develop an algorithm that can adjust the approximation ratio. Extensive experiments verified that, FR2FP-ex demonstrates the best result quality, and it is very close to the optimal solution. In addition, we also unveil the scenarios when the state-of-the-art would fail. We further generalize the k-FR problem, considering the budget for relocation and the cost of each facility. We also present corresponding approximate solutions toward the new problem and prove the approximation ratio.

Automated summary

Facility Relocation (FR) has a significant impact on many areas, but existing solutions fail to guarantee the quality of relocating multiple facilities. We propose a transformation approach to solve the k-FR problem by converting it into a submodular and non-decreasing facility placement problem. We present the first approximate solution, FR2FP, and further improve it with FR2FP-ex. Extensive experiments demonstrate that FR2FP-ex achieves the best result quality and is very close to the optimal solution. We also generalize the k-FR problem by considering relocation budget and facility cost, and provide approximate solutions with proven approximation ratios.