Planar Weber location problems with barriers and block norms

Horst Hamacher and Kathrin Klamroth

Annals of Operations Research, 2000, vol. 96, issue 1, 208 pages

Abstract: 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

Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018951502447 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:96:y:2000:i:1:p:191-208:10.1023/a:1018951502447

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018951502447

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().