Geoscience Reference
In-Depth Information
Chapter 13
The Quadratic Assignment Problem
Zvi Drezner
Abstract
The quadratic assignment problem is reviewed in this chapter. Weights
between pairs of facilities and distances between the same number of locations
are given. The problem is to find the assignment of facilities to locations that
minimizes the weighted sum of distances. This problem is considered to be one of
the most difficult combinatorial optimization problems. The construction of efficient
solution algorithms (exact or heuristic) is challenging and has been extensively
investigated by the communities working in Operations Research/Management
Science, Industrial Engineering, or Computer Science. Examples of applications are
given, the related layout problem is briefly described, exact and heuristic solution
algorithms are reviewed, and a list of test problem instances and results are reported.
Keywords
Exact methods Metaheuristics Quadratic assignment
13.1
Introduction
The quadratic assignment problem (QAP) is considered one of the most difficult
optimization problems to solve optimally. The QAP is a combinatorial optimization
problem stated for the first time by Koopmans and Beckmann (
1957
). Early papers
on the subject include Gilmore (
1962
), Pierce and Crowston (
1971
), Lawler (
1973
),
and Love and Wong (
1976
). The problem is defined as follows. A set of n possible
sites are given and n facilities are to be located on these sites, one facility at a site.
Let c
ij
be the cost per unit distance between facilities i and j and d
ij
be the distance
between sites i and j.Thecostf to be minimized over all possible permutations,
calculated for an assignment of facility i to site p.i/ for i
D
1;:::;n,is:
X
n
X
n
f
D
c
ij
d
p.i/p.j/
(13.1)
iD1
jD1
