GOAL: a clustering-based method for the group optimal location problem

摘要

Optimal location problems are important problems and are particularly useful for strategic planning of resources. However, existing studies mainly focus on computing one or k optimal locations. We study the Group OptimAl Location (GOAL) problem, which computes a minimum set of locations such that establishing facilities at these locations guarantees that every facility user can access at least one facility within a given distance \(r\in {\mathcal {R}}^+\). We propose two algorithms, GOAL-Greedy and GOAL-DP, to first solve the problem in the Euclidean space. These two algorithms are supported by a clustering-based method to compute an initial solution of the problem, which yields an upper bound of the number of locations needed to solve the problem. We propose a grid partitioning-based strategy to refine the initial solution and obtain the final solution. We further extend our algorithms to road networks. We perform extensive experiments on the proposed algorithms. The results show that the proposed algorithms can solve the problem effectively and efficiently in both Euclidean spaces and road networks.