×

Weber’s problem with attraction and repulsion under polyhedral gauges. (English) Zbl 0891.90098

Summary: Given a finite set of points in the plane and a forbidden region \({\mathcal R}\), we want to find a point \(X\not\in\text{int}({\mathcal R})\), such that the weighted sum to all given points is minimized. This location problem is a variant of the well-known Weber problem, where we measure the distance by polyhedral gauges and allow each of the weights to be positive or negative. The unit ball of a polyhedral gauge may be any convex polyhedron containing the origin. This large class of distance functions allows very general (practical) settings – such as asymmetry – to be modeled. Each given point is allowed to have its own gauge and the forbidden region \({\mathcal R}\) enables us to include negative information in the model. Additionally, the use of negative and positive weights allows to include the level of attraction or dislikeness of a new facility. Polynomial algorithms and structural properties for this global optimization problem (d.c. objective function and a non-convex feasible set) based on combinatorial and geometrical method are presented.

MSC:

90B80 Discrete location and assignment
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI