Geoscience Reference
In-Depth Information
Eq. (
13.1
), by exchanging the sites of facilities r and s.Therearen.n
1/=2 such
values. It can be easily verified that:
n
X
˚
c
ir
d
p.i/p.s/
d
.p.i/p.r/
C
c
is
d
p.i/p.r/
d
.p.i/p.s/
f
rs
D
2
iD1
X
n
˚
Œc
ir
c
is
d
p.i/p.r/
d
p.i/p.s/
:
D
2
(13.3)
iD1
Calculating f
rs
by (
13.3
) requires only O.n/ time rather than O.n
2
/ time.
Taillard (
1991
) points to yet a faster formula for calculating f
rs
.Let
u
v
f
rs
be
the variation in the value of the objective function corresponding to exchanging
u
and v given that the previous exchange involved r and s, and assuming
u
and v
different from r and s. This change in the value of the objective function can be
calculated in O.1/ time starting from the second iteration. The formula is based
on f
u
v
(the change in the value of the objective function from the previous
permutation by exchanging the pair
u
v). Therefore, one needs to keep all the values
of f
ij
for all pairs i;j. Saving these values requires O.n
2
/ time for each evaluation
of all pair exchanges. It can be easily verified by (
13.3
)that:
u
v
f
rs
D
f
uv
C
2Œc
su
C
c
rv
c
sv
c
ru
d
p.s/p.
u
/
C
d
p.r/p.v/
d
p.s/p.v/
d
p.r/p.
u
/
;
which is calculated in O.1/ time. Note that only 2n
3 pairs are not mutually
exclusive and formula (
13.3
) can be used in these cases to evaluate f
rs
. Therefore,
evaluating the change in the value of the objective function for all n.n
1/=2
possible pair exchanges requires O.n
2
/ time rather than O.n
4
/ time.
Many metaheuristic approaches have been suggested for solving the QAP. For
example, simulated annealing was proposed by Wilhelm and Ward (
1987
), Connoly
(
1990
), Misevicius (
2003
), ant colonies was investigated by Gambardella et al.
(
1999
), Taillard (
1998
,
2000
), Talbi et al. (
2001
), migrating birds optimization was
suggested by Duman et al. (
2012
), scatter search was implemented by Cung et al.
(
1997
), simulated jumping was proposed by Amin (
1999
) and a greedy randomized
adaptive search procedure was designed by Li et al. (
1994
) and Oliveira et al. (
2004
).
Various versions of the metaheuristic tabu search (Glover
1977
,
1986
; Glover
and Laguna
1997
) were suggested for the solution of the QAP. Skorin-Kapov
(
1990
) proposed the first application of tabu search followed by Taillard (
1991
)
who proposed the Robust Tabu. The latter remained as the most powerful heuristic
approach for many years. The tabu list is set to contain pairs of facility-site (i.e.,
there are n
2
possible entries in the tabu list). There is a short term and long term
tabu memory.
Short Term Memory: When a facility is removed from a site, the iteration number
is recorded. An exchange between two facilities is not allowed (unless the
objective function is better than the best one found so far) if both facilities move
