The single facility location problem with minimum distance constraints

The single facility location problem with minimum distance constraints

0.00 Avg rating0 Votes
Article ID: iaor19991619
Country: United Kingdom
Volume: 5
Issue: 3
Start Page Number: 147
End Page Number: 163
Publication Date: Oct 1997
Journal: Location Science
Authors: ,
Keywords: facilities
Abstract:

We consider the problem of locating a single facility (server) in the plane, where the location of the facility is restricted to be outside a specified forbidden region (neighborhood) around each demand point. Two models are discussed. In the restricted 1-median model, the objective is to minimize the sum of the weighted rectilinear distances from the n customers to the facility. We present an O(n log n) algorithm for this model, improving upon the O(n3) complexity bound of the algorithm by Brimberg and Wesolowsky. In the restricted 1-center model the objective is to minimize the maximum of the weighted rectilinear distances between the customers and the serving facility. We present an O(n log n) algorithm for finding an optimal 1-center. We also discuss some related models, involving the Euclidean norm.

Reviews

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