Article ID Journal Published Year Pages File Type
474145 Computers & Operations Research 2008 13 Pages PDF
Abstract

The 1-center problem in the plane with random weights has only been studied for a few specific probability distributions and distance measures. In this paper we deal with this problem in a general framework, where weights are supposed to be independent random variables with arbitrary probability distributions and distances are measured by any norm function. Two objective functions are considered to evaluate the performance of any location. The first is defined as the probability of covering all demand points within a given threshold, the second is the threshold for which the probability of covering is bounded from below by a given value. We first present some properties related to the corresponding optimization problems, assuming random weights with both discrete and absolutely continuous probability distributions. For weights with discrete distributions, enumeration techniques can be used to solve the problems. For weights continuously distributed, interval branch and bound algorithms are proposed to solve the problems whatever the probability distributions are. Computational experience using the uniform and the gamma probability distributions is reported.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,