Demand Point Aggregation for Some Basic Location Models - Location Science - page 484

heuristic location minimization algorithms to compute . Thus doing aggregation
may be viewed as solving a location problem.
We remark for PMM, if S is restricted to being in a finite set of possible sites, and
there are fixed site costs but the sites are not aggregated, then the site fixed costs can
be added to the objective function without affecting the error bound.
Francis et al. ( 2009 ) give an extensive discussion of the use of the above error
bounds for aggregation. The conditions for the PMM error bound to be tight are
much stronger than for the PCM error bound to be tight, and this is reflected by better
computational experience for the PCM than the PMM. However, computational
experience does show that the PMM error bound is well correlated with sample
absolute error measures, and that it makes sense to locate ADPs so as to keep the
PMM error bound small.
Another location problem of interest is the covering location model, defined by
Example 3. Since D ( S , v j ) r j is equivalent to D ( S , v j ) /r j 1, from ( 18.1 ) we obtain
LJ LJ LJ

D S;v 0 j =r j -D S;v j =r j LJ LJ LJ d v 0 j ;v j =r j ; for all j 2 J and all S ǝ:

(18.2)

Thus we obtain n error bounds, one for each original constraint. Clearly, it makes
sense to aggregate so as to keep these error bounds small.
Let us now build on ( 18.2 ), the basic error bound idea for constraints. Generally,
we have location constraints of the form f j ( S ) r j , j 2 J , S ǝ. Suppose each
function f j ( S ) is replaced by some approximating function, say f j ( S ), resulting
in some constraints that are not distinct for the aggregated model of f j .S/
r j ;j 2 J; S ǝ. If we now define functions f ( S )and f 0 ( S )by f ( S ) max f ( 1/r j )

f j ( S ): j 2 J g , f 0 .S/ max n 1=r j f j .S/ W j 2 J o , then the constraints for the two
models are equivalent to f ( S ) 1and f 0 ( S ) 1 respectively. Hence we can view f 0 ( S )
as an aggregated version of the function f ( S ), and apply whatever function error
measures are of interest. It is known (Francis et al. 2004a , b , c ) for example, that if

f j ( S )and f j ( S ) have error bound b j D d v 0 j ;v j =r j for the CLM for j 2 J ,then
f ( S )and f 0 ( S ) have the (unitless) error bound eb D max f b j : j 2 J g . For the CLM, the
resulting error bound is identical in form to that for the PCM; hence aggregation
methods providing small PCM error bounds also can provide small CLM error
bounds, and vice-versa.
When f ( S )and f 0 ( S ) are any original and aggregated functions with some error
bound eb , it follows directly that f 0 .S/ 1 eb ) f.S/ 1 I f.S/ 1 )
f 0 .S/ 1 C eb . Thus the constraint f 0 ( S ) 1 eb gives a restriction of the original
constraint, while f 0 ( S ) 1 C eb gives a relaxation. Each can be easier to deal with
than the original constraint and may be used to compute lower and upper bounds
on the optimal objective function value of the original model. Supposing eb 1
(which is clearly desirable), feasibility conclusions about one model thus allow us
to draw feasibility or “near-feasibility” conclusions about the other model.