Geoscience Reference
In-Depth Information
a
b
Fig. 23.3
Districting plans for two center-based
compactness
measures
without contiguity.
(
a
) Districts for
cmp
ud
./.(
b
) Districts for
cmp
wd
2
./
and its basic units. Variations exist in whether the distances are weighted with
activity measures or not (w/u) and whether distances are squared or not (d
2
/d)
cmp
ud
.D
k
/
D
X
j2D
k
cmp
ud
2
.D
k
/
D
X
j2D
k
d
c
k
;j
d
c
k
;j
cmp
wd
.D
k
/
D
X
j2D
k
cmp
wd
2
.D
k
/
D
X
j2D
k
w
j
d
c
k
;j
w
j
d
c
k
;j
(Bard and Jarrah
2009
;Bergeyetal.
2003
; Hess and Samuels
1971
; Zoltners and
Sinha
2005
). The second and forth measure are also known as the (weighted)
moment of inertia (Hess et al.
1965
). Although the four local compactness measures
follow the same idea, the resulting districts may look considerably different as the
following example shows.
Example 23.2
Consider a point set of n
D
75 basic units that has to be partitioned
into p
D
5 districts, each having a predetermined center. The allowed relative
deviation in terms of balance from the mean district size is 5 %, and contiguity
is not explicitly imposed. Figure
23.3
shows the resulting districting plans that
minimize the sum of the two center-based compactness measures
cmp
ud
.
/ and
cmp
wd
2
.
/ over all districts. The enlarged icons represent the district centers.
Having in mind that compactness acts as a proxy for travel times, the most natural
measure is
cmp
ud
.
/. However, we observe that there is a considerable overlap in
the districts for this measure, especially between the districts represented by the
diamond and pentagon shaped basic units. A much better visual separation is instead
obtained for the weighted squared distance,
cmp
wd
2
.
/, even if some district centers
now lie outside their actual district (again, diamonds and pentagons). A large overlap
between districts typically yields less efficient routes for sales persons. To underline
this observation, we determine for each district the TSP tour through all basic units,
including the center. The total lengths of the TSP tours for the two districting plans
are: 92.78 and 73.56. The travel distances for the weighted squared distance are
20 % smaller than for
cmp
ud
.
/. The results for
cmp
wd
.
/ and
cmp
ud
2
.
/ in terms of
