Geoscience Reference
In-Depth Information
Fig. 2.7 Errors due to using
a genetic algorithm
Percent Error for Genec Algorithms
12%
10%
8%
6%
4%
2%
0%
0
5
10
15
20
25
Number of Medians
Gen Alg
Gen Alg w Subs
2.7
Multi-objective Extensions of the p -Median Model
The formulation above, ( 2.1 )-( 2.6 ), can be modified to obtain a formulation of the
maximum covering problem (Church and ReVelle 1974 ). The maximum covering
problem finds the location of p facilities to maximize the number of demand nodes
that are covered within some coverage distance, d c . In particular, we let d ij be the
distance between candidate site i 2
I
and demand node j 2
J
. We then define
c ij D 0 if d ij d c
1 if d ij >d c :
b
If we now solve ( 2.1 )-( 2.6 ) with c ij replaced by c ij , we will be able to solve a
maximum covering problem. In essence, we are minimizing the total number of
uncovered demands, which is equivalent to maximizing the number of covered
demands.
We can also find the tradeoff between the covering and average cost (or average
distance) objective by minimizing a suitable linear combination of the two cost
terms. In particular, we minimize a weighted sum Q c ij D Ǜc ij C .1 Ǜ/ O c ij of the
original c ij and the coverage term c ij , with 0 Ǜ 1.Clearly,ifǛ D 1, the model
will simply minimize the demand weighted total distance or cost. Also, if Ǜ D 0,
the model will minimize the number of uncovered demands.
The choice of Ǜ is critical if we want to trace out the complete tradeoff curve.
Many researchers and practitioners simply solve the problem for fixed values of Ǜ.
For example, they might solve the problem for Ǜ D 0; 0:05; 0:1;:::;1:0.Wedo
not recommend this approach because it is simultaneously likely to miss important
points on the tradeoff curve and to result in obtaining many identical solutions.
Search WWH ::




Custom Search