Geoscience Reference
In-Depth Information
Finally, if the underlying road network is given, yet another possibility is to define
two basic units as being adjacent, if the shortest path between the two does not
contain another basic unit.
23.4.3.2
Geometric Measures
If no neighborhood information for basic units is given or can reasonably be derived,
an alternative is to determine the overlap between the districts. For example, by
computing the convex hull
ch
.D
k
/ around each district D
k
and defining a district to
be contiguous if no basic unit of another district lies in its convex hull, i.e.,
ch
.D
k
/
\
ch
.D
l
/
D;
,
8
l
¤
k (Kalcsics et al.
2005
; Jarrah and Bard
2012
). One advantage
of this approach is that convex districts usually prevent the crossing of routes of
different districts, a characteristic that typically implies inefficient routes.
23.4.3.3
Mathematical Modelling
In districting models, contiguity is always treated as a hard constraint (except in
Hanafi et al.
1999
). One possibility to include it in a mathematical programming
formulation is the following: Let c
k
2
J
c
be the predetermined center of district k
and S
J
nf
N.c
k
/
[f
c
k
gg
be a subset of basic units that are not adjacent to c
k
.If
all elements of S are assigned to k, i.e., S
D
k
, then at least one basic unit not in
S that is adjacent to an element of S must also be assigned to k:
X
x
kj
X
j2S
x
kj
1
j
S
j
S
J
nf
N.c
k
/
[f
c
k
gg
;
j2
S
i2S
N.i/nS
where x
kj
is 1 if j
2
J is assigned to district k and 0 otherwise (Drexl and Haase
1999
). The drawback of this formulation is, that it requires an exponential number
of constraints (although it gives naturally rise to a cut generation approach, Ríos-
Mercado and López-Pérez
2013
). A second possibility that only needs a linear
number of constraints is based on network flow constraints. Each basic unit has
one unit of supply, and the district centers act as sinks. District k is contiguous iff
there exists a flow from its basic units to c
k
that only passes basic units in D
k
:
X
f
ji
X
i2N.j/
f
ij
D
x
kj
8
j
2
J
nf
c
k
g
i2N.j/
X
f
ij
.n
2/x
kj
8
j
2
J
nf
c
k
g
i2N.j/
X
f
i;c
k
n
1;
i2N.c
k
/
