Geoscience Reference
In-Depth Information
23.5.2
Set-Partitioning Models
As districting is essentially a partitioning problem, classical set partitioning
approaches can be used to solve the problem. In a first step, balanced, contiguous,
and compact candidate districts are generated in a heuristic fashion. In a second step,
districts are selected from the set of candidates to optimize the overall balance of the
district plan (Garfinkel and Nemhauser
1970
; Mehrotra et al.
1998
). Unfortunately,
only small instances can be solved optimally with this approach. An advantage
compared to location-allocation methods is however that almost any criterion can
be applied on the generation of candidate districts.
23.5.3
Computational Geometry Methods
A very simple but efficient solution approach for basic units representing points
is the successive dichotomies strategy (Kalcsics et al.
2005
).Themainideaisto
recursively subdivide the problem geometrically using lines into smaller and smaller
subproblems until an elementary level is reached, where the problem can be solved
efficiently. Hence, the basic operation is to partition a subset J
0
of basic units into
two subsets J
l
and J
r
by drawing a line within this set of points. Given a number
of line directions, for each direction the position of the line is determined in such
a way that the two resulting subproblems are best balanced. For every direction,
the line is evaluated by a convex combination of its balance and its compactness
(evaluated through the length of inter-district boundaries), and the best line is then
used to divide the problem into two subproblems. This procedure is repeated until
every subset corresponds to a single district. The strategy quickly determines a well-
balanced districting plan with no overlap between districts. However, as it does
not explicitly account for (road) distances, the resulting districts sometimes lack
compactness. Moreover, it is difficult to include neighborhood information. Instead
of using lines, other geometric concepts can be used. Alternatively, the process of
subdividing a point set J
0
can be modeled and solved as a 2-facility location problem
(Salazar-Aguilar et al.
2013a
).
Example 23.4
Consider again the example in Fig.
23.3
and assume that the district
centers are flexible. Figure
23.6
shows the districting plan obtained with the
successive dichotomies algorithm using horizontal, vertical, and diagonal lines.
Another approach is based on weighted Voronoi diagrams on networks (for a
definition of weighted Voronoi diagrams see Aurenhammar et al.
2013
). Assume
that the neighborhood graph G is given. For center-based measures the most
compact solution is obtained by assigning each basic unit to the closest center. If
the distances
f
d
c
k
;j
j
c
k
2
J
c
g
are unique for each j
2
J, then each district
will also be connected. However, the resulting districts are often far from being
balanced. To overcome this drawback, the idea is to modify the distances d
c
k
;j
