Districting Problems - Location Science - page 585

23.4.2 Balance

This criterion is one of the trademarks of districting problems. It expresses the desire
for districts of equitable size with respect to the activity measure(s). In political
districting, this criterion is employed to ensure the “one man-one vote” principle,
and in sales territory design to avoid districting plans with large discrepancies in
terms of workload, sales potential, or travel time.
Due to the discrete structure of the problem and the integrity assumption,
perfectly balanced districts can generally not be accomplished. There exist different
approaches in the literature to quantify imbalance and to incorporate the criterion
into the districting process. The most common local measure is based on the relative
deviation of the district size w .D k / from the mean district size D w .J/=p:
bal .D k / D LJ LJ LJ LJ

LJ LJ LJ LJ

w .D k /

; 1 k p

(cf. Forman and Yue 2003 ; Ríos-Mercado and Fernández 2009 ; Silva de Assis et al.
2014 ). The larger this deviation is, the worse is the balance. A district D k is perfectly
balanced, if bal .D k / D 0. If the district sizes also contain a solution dependent
performance measure, like travel times, then this affects and the balance of
one and the same district may be different in different districting plans. Another
approach concedes a priori a certain relative deviation Ǜ>0from perfect balance
and only measures the imbalance exceeding this threshold (Bodin and Levy 1991 ;
Bozkaya et al. 2011 )

bal .D k / D 1

max f w .D k / .1 C Ǜ/; .1 Ǜ/ w .D k /; 0 g ;

i.e., the district is balanced if its size is between this lower and upper bound. Instead
of determining the bounds based on the mean district size, they are sometimes
directly motivated by the application, e.g., the working time restrictions of the
mailman or the sales potential required to ensure a decent living for the sales person.
Using these local measures, the global balance of a districting plan is then
typically computed as the maximal balance of a district

bal max .

D

/ D max

kD1;:::;p bal .D k /:

Less common are the sum over all districts (Bozkaya et al. 2003 ; Bodin and Levy
1991 ) or a convex combination of both (Butsch et al. 2014 ):

p

X

bal sum . bal cv . / D bal sum . / C .1 / bal max . D / D bal .D k / and D D D /;

kD1