78
5 Extensions and Related Problems
The number of floors and elevators is assumed to be fixed; if necessary, we could
run the model for several different options. The floor dimensions are also assumed
to be fixed, but they could easily be treated as decision variables.
For simplicity in the formulation, and without loss of generality, we assume that
the elevators represent all the necessary systems for vertical movement between
floors, including actual elevators, stairs, water pipes, and air ducts. For this reason,
the dimensions of the elevators and/or restrictions on their possible locations are
frequently given as part of the problem description.
We consider the problem of determining the optimal locations of the elevators,
and the optimal locations and dimensions of the departments. The horizontal
distance is the rectilinear distance (which is a reliable measure, as in the singlefloor case), but the vertical distance must take into account the use of the elevators.
This makes the formulation more complex.
Let δ be the ceiling height, p the number of floors, and e the number of elevators.
Set M = w F + h F + δp, and define the following variables:
z ik = 1 if department i is assigned to floor k, 0 otherwise;
Z ij = 1 if departments i and j are allocated to the same floor, 0 otherwise;
X ij , Y ij : binary variables used to set up the nonoverlap constraints;
(x i , y i ): coordinates of the centre of department i;
d v
ij : vertical distance between departments i and j ;
d
h
ij : horizontal distance between departments i and j ;
where the indices 1, . . . , n correspond to the departments, and the indices n +
1, . . . , n + e correspond to the elevators.
We can formulate the MF-FLP as follows:
minimize
1≤i
ij + d v
ij )
(5.6)
s.t.
p
k=1
z ik = 1, 1 ≤ i ≤ n
(5.7)
Z ij ≥ z ik + z jk − 1, 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.8)
Z ij ≤ 1 − z ik + z jk , 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.9)
Z ij ≤ 1 + z ik − z jk , 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.10)
d v
ij = δ
p
k=1
k(z ik − z jk )
, 1 ≤ i < j ≤ n
(5.11)
d h
ij ≥ |x i − x j | + |y i − y j |, 1 ≤ i < j ≤ n
(5.12)
d h
ij ≥ |x i − x | + |y i − y | + |x j − x | + |y j − y | − 2(w F + h F ) Z ij ,
(5.13)
5 Extensions and Related Problems
The number of floors and elevators is assumed to be fixed; if necessary, we could
run the model for several different options. The floor dimensions are also assumed
to be fixed, but they could easily be treated as decision variables.
For simplicity in the formulation, and without loss of generality, we assume that
the elevators represent all the necessary systems for vertical movement between
floors, including actual elevators, stairs, water pipes, and air ducts. For this reason,
the dimensions of the elevators and/or restrictions on their possible locations are
frequently given as part of the problem description.
We consider the problem of determining the optimal locations of the elevators,
and the optimal locations and dimensions of the departments. The horizontal
distance is the rectilinear distance (which is a reliable measure, as in the singlefloor case), but the vertical distance must take into account the use of the elevators.
This makes the formulation more complex.
Let δ be the ceiling height, p the number of floors, and e the number of elevators.
Set M = w F + h F + δp, and define the following variables:
z ik = 1 if department i is assigned to floor k, 0 otherwise;
Z ij = 1 if departments i and j are allocated to the same floor, 0 otherwise;
X ij , Y ij : binary variables used to set up the nonoverlap constraints;
(x i , y i ): coordinates of the centre of department i;
d v
ij : vertical distance between departments i and j ;
d
h
ij : horizontal distance between departments i and j ;
where the indices 1, . . . , n correspond to the departments, and the indices n +
1, . . . , n + e correspond to the elevators.
We can formulate the MF-FLP as follows:
minimize
1≤i
ij + d v
ij )
(5.6)
s.t.
p
k=1
z ik = 1, 1 ≤ i ≤ n
(5.7)
Z ij ≥ z ik + z jk − 1, 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.8)
Z ij ≤ 1 − z ik + z jk , 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.9)
Z ij ≤ 1 + z ik − z jk , 1 ≤ i < j ≤ n, k = 1, . . . , p
(5.10)
d v
ij = δ
p
k=1
k(z ik − z jk )
, 1 ≤ i < j ≤ n
(5.11)
d h
ij ≥ |x i − x j | + |y i − y j |, 1 ≤ i < j ≤ n
(5.12)
d h
ij ≥ |x i − x | + |y i − y | + |x j − x | + |y j − y | − 2(w F + h F ) Z ij ,
(5.13)