Scholarlink

<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\frac{1}{n}\)</EquationSource> </InlineEquation> as the number of demand points <i>n</i> 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 <i>n</i>. Using a geometric proof for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n=3\)</EquationSource> </InlineEquation> 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, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\frac{1}{3}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\frac{1}{4}\)</EquationSource> </InlineEquation>. For larger values of <i>n</i>, 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\frac{1}{n}\)</EquationSource> </InlineEquation> for all <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(n\ge 3\)</EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年9月19日

查看全文
  • Pawel Kalczynski,
  • Jack Brimberg,
  • Zvi Drezner

摘要

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\) .