On the probability that the optimal solution of the Weber location problem is at a demand point

The Weber problem requires finding the location of a new facility that minimizes a sum of weighted Euclidean distances to a set of given demand points in the plane. An open question relates to the probability that the optimal location coincides with a demand point. This question is not only of theoretical interest, but also of practical importance, since the convergence rate of popular algorithms used to solve the Weber problem may be sub-linear when the optimal solution occurs at a demand point, while the rate is linear if this does not occur. It has been shown by simulation that for the unweighted problem which we consider in this paper, and demand points uniformly distributed in a disc, this probability approaches $$\frac{1}{n}$$ as the number of demand points n becomes large. In practical problems where several new facilities need to be located, the average number of demand points assigned to each one can be relatively small. For this reason, it is also important to consider this probability for small values of n. Using a geometric proof for $$n=3$$ and 4, we show here that when demand points can be located anywhere in the plane (i.e., a region with unspecified boundaries), the probabilities are, respectively, $$\frac{1}{3}$$ and $$\frac{1}{4}$$ . For larger values of n, there is no known geometric argument. However, using a novel approach to describe a uniform distribution of the demand points anywhere in the plane, we are able to apply known properties of the planar random walk to prove that the probability is exactly $$\frac{1}{n}$$ for all $$n\ge 3$$ .