Geoscience Reference
In-Depth Information
X
w
j
x
ij
.1
Ǜ/y
i
8
i
2
J
(23.3)
j2J
X
w
j
x
ij
.1
C
Ǜ/y
i
8
i
2
J
(23.4)
j2J
X
y
i
D
p
(23.5)
i2J
y
i
;x
ij
2f
0;1
g
8
i;j
2
J;
(23.6)
where x
ij
D
1 if basic unit j is assigned to basic unit i, 0 otherwise, and
y
i
D
1 if basic unit i is selected as district center, 0 otherwise. The objective
function (
23.1
) maximizes the compactness of the districts using the center-
based measure
cmp
wd
2
.
/. Constraints (
23.2
), together with the integrality con-
straints on the x
ij
-variables, model the unique and exclusive assignment criterion.
Constraints (
23.3
)and(
23.4
) restrict the balance of the districts. Finally, Con-
straints (
23.5
) ensure that exactly p basic units are selected as district centers. As a
result, all basic units allocated to the same basic unit i constitute a district with the
basic unit as its center, i.e., there is a one-to-one correspondence between centers
and districts. Note that the centers are just required to evaluate district compactness
and have no meaning in itself.
Unfortunately, due to its NP-hardness, the practical use of this formulation is
limited to instances with a few hundred basic units, which is rather small for
typical sales districting problems. To this end, Hess et al. (
1965
) propose to use
Cooper's location-allocation heuristic to solve the problem. In this heuristic, the
simultaneous location and allocation decisions of the underlying facility location
problem are decomposed into two independent phases, a location and an allocation
phase, which are alternatingly performed until a satisfactory result is obtained. In
the location phase, a set J
c
of district centers is determined. A fairly simple and
commonly used method is to solve in each district resulting from the last allocation
phase a single facility location problem with the respective compactness measure
as objective function (cf. Fleischmann and Paraschis
1988
;Georgeetal.
1997
).
To obtain an initial set of centers, one can determine new centers based on the
solution of a Lagrangean subproblem (Hojati
1996
). Alternatively, one can use any
of the heuristics for the (uncapacitated) p-median problem or one of the heuristics
mentioned below.
Once the centers have been fixed, the allocation phase determines a balanced
assignment of basic units to district centers. This can be done by fixing y
i
D
1 for all
i
2
J
c
in the above formulation. With present-day computers and MIP solvers, the
resulting problem can be solved optimally even for large instances with 10,000 basic
units or more within a short time. Even in the presence of contiguity constraints,
several thousand basic units can be assigned in reasonable time (Ríos-Mercado
and López-Pérez
2013
). Alternatively, the allocation problem can be modeled as
a minimum cost network flow problem allowing more flexibility for measuring and
optimizing the balance and compactness of districts (George et al.
1997
).
