Geoscience Reference
In-Depth Information
Line location with the partial coverage objective function is equivalent to locating
a strip of given width and has recently been considered in Brimberg et al. (
2013b
).
7.5.1.3
A General Approach Based on dc-Programming
Blanquero et al. (
2009
) deal with the location of a variety of dimensional facilities
such as segments, arcs of circumferences, arbitrary convex sets, their complements,
or their boundaries. The idea is to fix the shape of the dimensional facility and to
look for a shift vector and an angle of rotation. The objective they follow is very
general, including most objective functions used in location theory, and allows also
to model obnoxious or semi-obnoxious location problems as follows: The set of
existing facilities is split into a subset V
C
for which the new facility is attractive
and a subset V
for which the new facility has negative effects. The distance from
the new facility to an existing point should be small when the point is in V
C
and
large when it is in V
. In order to combine the distances within the same set V
C
and V
Blanquero et al. (
2009
) propose to evaluate the norm (or the gauge) of the
resulting single distances.
Using that the Euclidean distance d.S;v/between a point and a set can be written
as difference of convex functions, Blanquero et al. (
2009
) solve the model by d.c.-
programming methods, outer approximation and branch and bound.
7.6
Conclusions
For the location of dimensional facilities we can draw the following conclusions.
The location of a one-dimensional facility (i.e., a point) and a two-dimensional
facility of convex shape with respect to a norm are convex problems if distances
are measured by norms.
In contrast, the location of a one-dimensional facility with respect to a norm is
a non-convex problem which usually has many locally optimal solutions. Only
the vertical distance leads to convex hyperplane location problems (if also the
objective function g is convex).
However, many of the investigated problems of locating a one-dimensional
facility are piecewise quasiconcave on a cell structure in dual space. This leads to
a finite dominating set. Another possibility for deriving an FDS is via Helly-type
theorems.
When distances are measured w.r.t a block norm, problems are often piecewise
linear and can hence be solved by linear programming methods.
The halving property holds when the problem is linear with respect to one of its
variables.
The main properties pointed out in this chapter are summarized in Table
7.2
.
They have the following algorithmic consequences.
