Geoscience Reference
In-Depth Information
Fig. 23.6
Districting plan
with the successive
dichotomies algorithm
between basic units and centers in such a way that assignments to overly large
districts are “penalized” and allocations to too small districts are “stipulated”. There
are basically two options to modify distances. The first adds a real-valued weight
r
k
2
to each distance d
c
k
;j
(Zoltners and Sinha
1983
) and the second multiplies
d
c
k
;j
by a positive weight r
k
2
R
R
C
(Ricca et al.
2008
). Hence, basic unit j
2
J
is closer to center c
k
than to center c
l
2
J
c
if d
c
k
;j
C
w
k
<d
c
l
;j
C
w
l
or
w
k
d
c
k
;j
<
w
l
d
c
l
;j
, respectively. Increasing (decreasing) the weight for a specific
center c
k
while keeping the other weights unchanged, will reduce (increase) the
number of basic units assigned to c
k
under the closest assignment rule and thus
reduce (increase) the size of the district. To obtain balanced districts, the weights
have to be updated iteratively until a satisfactory result is obtained. During the
update, care has to be taken because some districts may turn out empty under
additive weights or become disconnected for multiplicative weights if the weights
are too uneven. For details on the update procedures see Zoltners and Sinha (
1983
)
and Ricca et al. (
2008
). The partitions of the graph induced by these weights are
the so-called additively and multiplicatively weighted Voronoi diagrams. Note that
the approach using additive weights is in fact a Lagrangean relaxation where the
balancing constraints have been relaxed.
Most districting problems are solved using discrete models. However, these
problems (and a number of other logistics problems as well) can be converted into
problems with continuous demand functions. Continuous demand approximations
models are based on the spatial density and distribution of demand rather than on
precise information on every demand point. Given continuous approximations, one
can for example use Voronoi diagrams to compute or to smooth existing districts
(Galvão et al.
2006
), or determine perfectly balanced districts (Carlsson and Delage
2013
).
23.5.4
Construction Methods
There exist several easy approaches for constructing a districting plan from scratch.
One of the most popular ones is based on the multi-kernel growth methodology first
introduced in Vickrey (
1961
). The general idea of this methodology is to select
a certain number of basic units as “seed centers” and then assign to each seed
