Geoscience Reference
In-Depth Information
allocation from the old to the new districting plan should be kept small (Silva de
Assis et al.
2014
). Especially in sales territory design, customers often have a
preferred sales representative by whom they want to be serviced or vice-versa,
i.e., customers have banned salesmen (cf. Ríos-Mercado and López-Pérez
2013
).
Another criterion concerns the number of districts. Typically, p is predetermined
such that, for example, the expected workload in a district neither exceeds the
working time restriction of a deliverer nor renders him underutilized. If however
travel times within a district account for a large portion of the total working time,
then it is not always possible to fix p a priori since travel times strongly depend on
the shape of districts, i.e., their compactness. Therefore, sometimes p is a design
criterion (cf. Muyldermans et al.
2003
).
23.5
Solution Approaches
As with most optimization problems also for districting many different solution
approaches have been proposed in the literature over the years. These approaches
can roughly be divided in those that utilize a mathematical programming model and
those that depend merely upon heuristics. Among the former, location-allocation
and set partitioning methods have been discussed. The latter mainly focus on
geometric algorithms, simple construction methods, and classical meta heuristics,
like Tabu Search, GRASP, and Simulated Annealing. This section will present only
a rough overview and description of the most common approaches. Detailed reviews
can be found in Kalcsics et al. (
2005
) and Ricca et al. (
2013
).
23.5.1
Location-Allocation Methods
The first mathematical programming approach was proposed by Hess et al. (
1965
)
for political districting. They had the idea to model the problem as a capacitated
p-median facility location problem (see also Chap.
3
). Basic units correspond to
customers and their activity measure to their demand. The facilities to be located
are the district centers, and the capacity of the facilities is chosen in such a way that
the districts obtained by solving the problem are well balanced. Candidate locations
for the facilities are all basic units. For an allowed relative deviation Ǜ>0of the
district size from the mean district size , the formulation of Hess et al. (
1965
)is
minimize
X
i;j2J
w
j
d
ij
x
ij
(23.1)
subject to
X
i2J
x
ij
D
1
8
j
2
J
(23.2)
