Geoscience Reference
In-Depth Information
21.4.1
The Quadratic Assignment Problem
The well-known QAP (see Chap.
13
) as introduced by Koopmans and Beckmann
(
1957
) has been first applied to hospital layout planning by Elshafei (
1977
)who
developed heuristics to solve large instances of the problem since it is NP-hard. A
solution of the QAP determines the assignment of each OU j
2
J to a predefined
location (e.g., a room) i
2
I inside a building. It is assumed that each OU can be
assigned to each location. The solution of a QAP instance is an assignment of
j
J
j
OUs to
j
I
j
locations.
Denote by f
jk
the flow between each pair of OUs j;k
2
J. The distance between
each pair of locations h;i
2
I is given by d
hi
. A binary decision variable x
ij
can
be considered, indicating whether OU j is assigned to location i (x
ij
D
1)ornot
(x
ij
D
0). Moreover, we now assume that I
D
J
Df
1;:::;n
g
in order to obtain a
mathematical formulation of the QAP as follows:
minimize
X
h2I
X
X
X
f
jk
d
hi
x
hj
x
ik
(21.60)
i2I
j2J
k2J
subject to
X
i2I
x
ij
D
1
8
j
2
J
(21.61)
X
x
ij
D
1
8
i
2
I
(21.62)
j2J
x
ij
2f
0;1
g
8
i
2
I;j
2
J:
(21.63)
The objective function (
21.60
) minimizes the sum of all travel distances.
Constraints (
21.61
) ensure that each OU is assigned to exactly one room whereas
constraints (
21.62
) guarantee that each room is only occupied by one OU. Con-
straints (
21.63
) define the domain of the decision variables.
In this basic formulation of the QAP, the area and shapes of the OUs and locations
are not regarded explicitly. This means that each OU fits to each location. This is a
very strong assumption which is not realistic in many applications, such as hospital
layout planning, since the dimensions (area, length, width) of the OUs to be assigned
can vary in a wide range. In the next section, a MIP formulation is presented which
overcomes this drawback.
21.4.2
A Mixed-Integer Program
In contrast to the discrete layout representation by the QAP formulation, the MIP
formulation presented next allows for a continuous representation of the layout.
Thus, the length and width of each OU can be modeled explicitly as decision
variables considering the defined area of the OU. Furthermore, the location of each
OU can be chosen in a more flexible way within a given floor area, i.e., not only by
