Facility location problems with uncertainty on the plane

Facility location problems with uncertainty on the plane

0.00 Avg rating0 Votes
Article ID: iaor20052984
Country: Netherlands
Volume: 2
Issue: 1
Start Page Number: 3
End Page Number: 34
Publication Date: Mar 2005
Journal: Discrete Optimization
Authors: ,
Abstract:

We consider single facility location problems (1-median and weighted 1-center) on a plane with uncertain weights and coordinates of customers (demand points). Specifically, for each customer, only interval estimates for its weight and coordinates are known. It is required to find a “minmax regret” location, i.e. to minimize the worst-case loss in the objective function value that may occur because the decision is made without knowing the exact values of customers' weights and coordinates that will get realized. We present an O(n2log2n) algorithm for the interval data minmax regret rectilinear 1-median problem and an O(n log n) algorithm for the interval data minmax regret rectilinear weighted 1-center problem. For the case of Euclidean distances, we consider uncertainty only in customers' weights. We discuss possibilities of solving approximately the minmax regret Euclidean 1-median problem, and present an O(n22a(n)log2(n)) algorithm for solving the minmax regret Euclidean weighted 1-center problem, where a(n) is the inverse Ackermann function.

Reviews

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