Geoscience Reference
In-Depth Information
replaced by the distance between the centers of circles i and j. The solution method
is termed DISCON (dispersion concentration). In the dispersion phase all facilities
are put very close to one another and an explosion like the “big bang” disperses them
while they are attracted to one another by their weights as springs. At the end of the
process the circles are far from one another and in the concentration phase they
are moved back still attracted to one another by the weights. The solution for this
layout formulation of non-intersecting circles can be bounded or unbounded (when
some the weights are negative). Drezner (
1975
,
2010
) analyzed the issue of when
the solution is bounded or unbounded, and formulated necessary conditions and
sufficient conditions on the set of weights to determine whether the solution to this
formulation is bounded or unbounded. A different approach to heuristically solve
this problem by replacing the dispersion phase with the eigenvectors associated with
the second and third smallest eigenvalues of a certain matrix based on the weights,
was suggested by Drezner (
1987
). Armour and Buffa (
1963
) defined basic square
shaped “building blocks” and each facility consists of a given number of building
blocks and the shape of the facilities can be formed by having control over the
configuration of the set of building blocks associated with each facility.
13.4
Extensions
The three-index assignment problem (three-dimensional AP or 3AP), first suggested
by Pierskalla (
1967
,
1968
), is based on weights and distances defined by three
indices and the minimization requires two permutations rather than one.
The Generalized Quadratic Assignment problem (GQAP) was introduced by Lee
and Ma (
2005
). In this formulation the number of facilities is not necessarily equal
to the number of sites. Each site has a limited capacity to accommodate facilities.
The GQAP reduces to the standard QAP when the number of facilities is equal to
the number of sites, and the capacity of each site is one. Solution algorithms for the
GQAP can be found in Cordeau et al. (
2006
) and Hahn et al. (
2008
).
13.5
Exact Solution Algorithms
Designing an exact algorithm for solving the QAP is very difficult. Recently,
Fischetti et al. (
2012
) and Nyberg and Westerlund (
2012
) reformulated the problem
in ways that non-linear programming software can be applied to solve such
problems with limited success.
Even designing an effective lower bound to be used in a branch-and-bound
algorithm is not easy. The first lower bound was developed by Gilmore (
1962
)
and Lawler (
1973
). A linear programming based lower bound was suggested by
