Accelerated hyperbolic smoothing method for solving the multisource Fermat–Weber and k-Median problems

摘要

This article deals with the Multisource Fermat–Weber and continuous k-Median problems. The first problem is the continuous location–allocation problem, defined in a planar region, an important problem in facility location subject. The continuous k-Median problem, defined in a multidimensional space, is also known as the minimum sum-of-distances clustering problem. Their mathematical modellings lead to a min-sum-min formulation which is a global optimization problem with a bi-level nature, nondifferentiable and with many minimizers. To overcome these severe difficulties, the Hyperbolic Smoothing methodology is proposed, in connection with a partition of locations in two groups: location in the frontier and location in gravitational regions, which drastically simplify the computational tasks. For the purpose of illustrating both the reliability and the efficiency of the method, we perform a set of computational experiments making use of the traditional instances described in the literature. Apart from consistently presenting similar or even better results when compared to related approaches, the novel technique was able to deal with instances never tackled before, with up to 1243088 cities.