Geoscience Reference
In-Depth Information
a
b
Fig. 23.5 Illustration of one iteration of the location-allocation procedure. ( a ) Location phase:
new districts centers. ( b ) Allocation phase: new districts
Example 23.3 Consider again the example depicted in Fig. 23.3 , but assume now
that the district centers are flexible and the current ones are just a starting point.
Based on the districting plan for the measure cmp wd 2 . /, the new centers that
minimize cmp wd 2 . / over each district are shown on the left-hand side in Fig. 23.5 .
The subsequent allocation phase yields the new districts shown on the right-hand
side. The districts are visually much more compact and there is no overlap between
the convex hulls of the districts.
In former times, when the exact solution of the allocation problem was unattain-
able for larger instances, the assignment problem was solved heuristically. Setting
the tolerance Ǜ to zero and relaxing the integrality constraints on the assignment
variables, i.e., x ij 2 Œ0;1, the resulting linear program is a classical transportation
problem that can be solved efficiently using specialized network algorithms.
However, solving the relaxed problem yields districts that are perfectly balanced
but usually assign portions of basic units to more than one district, i.e., 9 i; i 0 2 J c ,
i ¤ i 0 , j 2 J, such that x ij ;x i 0 j >0. Such basic units are called splits. For an
optimal basic feasible solution of the transportation problem, it is easy to prove that
there are at most p 1 splits (Hojati 1996 ). To restore the integrity of basic units,
it is necessary to round for every split its fractional variables to one (one variable)
or zero (the other variables). This yields disjoint districts but destroys their perfect
balance. A simple split resolution rule is to assign a split to the district (center) that
“owns” the largest share of the split (Hess and Samuels 1971 ). However, if there
are just few basic units per district, this rule may produce very unbalanced districts.
An optimal split allocation with a minimal maximal percentage deviation can be
obtained in polynomial time by using tree partitioning methods; unfortunately, the
problem of finding a split resolution with a minimal total deviation is NP-hard; see
Schröder ( 2001 ) for details.
Search WWH ::




Custom Search