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

Table 18.4 Relaxation and restriction of both the original and aggregated covering location
models assuming all ı j < r j
Constructing aggregated CLM
1

Definitions 1 , :::, q : the q distinct ADPs

ı j d.v j ;v j /; j 2JI ı j <r j ;j2J
LJ i minfr j ı j W v i D v j g;i D 1;:::; q
i minfr j C ı j W v i D v j g;iD 1;:::;q

D S;v j r j ;j2J,all S 2 Original covering

constraints

D S;v j r j ; j2J,all S

3 Aggregate constraints

D S;v j r j ı j ;j2J; all S ()
D . S; i / LJ i ;iD 1;:::;q; all S

4 Restrictions of both original

and aggregate constraints

D S;v j r j C ı j ;j2J; all S ()
D.S; i / i ;iD 1;:::;q; all S

5 Relaxations of both original

and aggregate constraints

Following Francis et al. ( 2004b ), Table 18.4 illustrates the use of error bounds as
discussed to obtain a relaxation and restriction of the aggregated CLM as well as a
relaxation and restriction of the original model.
Francis et al. ( 2004b ) used the approach of Table 18.4 . They solved to optimality
a CLM with almost 70,000 original CLM constraints by solving several aggregated
CLMs each with less than 1,000 covering constraints. Their computational experi-
ence was usually that the minimal objective function value of the original model
was underestimated when solving the approximating model without enough ADPs,
which is consistent with the discussion in Sect. 18.2 . The case study of Sect. 18.3
uses some of these aggregation ideas.

The error bound max n w j d v 0 j ;v j W j 2 J o for the PCM and CLM for some
choice of the w j including w j D 1 /r j is quite robust. It applies to an obnoxious facility
location model (Francis et al. 2000 ); Erkut and Neuman 1989 ) and, when doubled,
to a p- center hub location model (Gavriliouk 2003 ; Ernst et al. 2002a , b ).

18.6 Conclusions

For location problems with hundreds of thousands of demand points, aggregation is
often essential. This chapter has dealt with the topic of demand point aggregation
for location models. We have pointed out that demand point aggregation causes
error, and presented some possible ways of measuring this error. Our focus has
been on the concept of an error bound, an upper bound on the maximum absolute
error due to aggregation. Error bounds are given for three key location models: the
p -median model (PMM), the p -center model (PCM) and covering location model
(CLM). We have shown that minimizing the error bounds for (PMM) or (PCM)
results in a location problem. This is a concept that we have called “the paradox