New local searches for solving the multi-source Weber problem

This paper presents three new heuristic approaches for the solution of the multi-source Weber problem in the plane: a constructive heuristic that finds a good starting solution, a decomposition approach which uses Delaunay triangulation, and a new efficient neighborhood structure based on the single facility limited distance median problem. A new heuristic incorporating all these approaches provided high quality solutions in reasonable computing time. We conclude that these heuristics successfully compete with the metaheuristic based methods found in the literature improving ten best known solutions. The ideas here may be extended to a variety of other continuous location as well as data mining problems.