Planar Weber location problems with barriers and block norms

The Weber problem for a given finite set of existing facilities Ex={Ex 1 ,Ex 2 ,...,Ex M }⊂∝ 2 with positive weights w m (m=1,...,M) is to find a new facility X * ∈∝ 2 such that Σ m=1 M w m d(X,Ex m ) 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. Copyright Kluwer Academic Publishers 2000