The 1-center problem in the plane with independent random weights

The 1-center problem in the plane with independent random weights

0.00 Avg rating0 Votes
Article ID: iaor2009851
Country: United Kingdom
Volume: 35
Issue: 3
Start Page Number: 737
End Page Number: 749
Publication Date: Mar 2008
Journal: Computers and Operations Research
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.