Planar Weber location problems with barriers and block norms

Planar Weber location problems with barriers and block norms

0.00 Avg rating0 Votes
Article ID: iaor20011673
Country: Netherlands
Volume: 96
Issue: 1
Start Page Number: 191
End Page Number: 208
Publication Date: Nov 2000
Journal: Annals of Operations Research
Authors: ,
Keywords: Weber problem
Abstract:

The Weber problem for a given finite set of existing facilities εx = {Ex1, Ex2, …, ExM} ⊂2 with positive weights wm (m = 1, …, M) is to find a new facility X* ∈ ℝ2 such that Mm=1 wmd(X, Exm) is minimized for some distance function d. In this paper we consider distances defined by block norms. A variation of this problem is obtained if barriers are introduced which are convex polyhedral subsets of the plane where neither location of new facilities nor traveling is allowed. Such barriers, like lakes, military regions, national parks or mountains, are frequently encountered in practice. From a mathematical point of view barrier problems are difficult, since the presence of barriers destroys the convexity of the objective function. Nevertheless, this paper establishes a discretization result: one of the grid points in the grid defined by the existing facilities and the fundamental directions of the polyhedral distances can be proved to be an optimal location. Thus the barrier problem can be solved with a polynomial algorithm.

Reviews

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