The Quadratic Assignment Problem - Location Science - page 333

9. Configuration of a large airport (Drezner et al. 2005 ). Many airports have
several terminals arranged in a partial star shape. Travel from one gate to
another in a different terminal requires passengers to go first to the center and
then to the other terminal. The weight c ij is the probability that a customer has
a connecting flight involving gates i and j.
10. Zoning a forest for different uses was proposed by Bos ( 1993 ). Land of a
particular suitability and location has to be assigned land use objectives in such
a way that the highest value is derived from zoning.
11. Scheduling parallel production lines proposed by Geoffrion and Graves ( 1976 ).
Production orders for a number of products must be scheduled on a number
of similar production lines so as to minimize the sum of product-dependent
changeover costs, production costs, and time-constraint penalties.
12. Assigning runners in a relay team. Heffley ( 1977 ) observed that, for example, in
a four person relay swimming competition each swimmer swims in a different
style. For each swimmer the time for each style is known. The coach needs to
select four swimmers, one for each style, such that the total time of all four
swimmers is minimized. This leads to a linear assignment problem. However,
in a runners relay when a baton needs to be transferred from one runner to the
next, the transfer time depends on the runner handing the baton and the one
receiving it. Suppose that the relay spans n runners and the problem is which
runner to assign to the first position, which one to the second, and so on. Let
us assume that run times following the transfer of the baton do not depend
on the position. Therefore, total run time depends on the total baton transfer
times. The cost matrix c ij is the baton transfer time from runner i to runner j.
The distances are all zeroes except that d i;iC1 D 1 for i D 1;:::;n 1.The
objective function of the resulting quadratic assignment problem is the sum of
all times of baton transfers.

13.3 The Layout Problem

The quadratic assignment problem seeks a permutation of equally sized facilities
to a given equally numbered set of locations. A similar situation is formulated
as the layout problem (Francis et al. 1992 ) where the locations of different sized
facilities are sought. Applications of such a problem are a floor layout of a plant, the
dashboard of an airplane instruments, layout of facilities, such as planed buildings,
in an area where the locations of the various facilities are flexible but an interaction
matrix representing the desirability of one facility to be close to another one is
given. The QAP can be viewed as a discrete location problem because the potential
locations for the facilities are given. In the layout problem the locations for the
facilities are not restricted to a given set of locations. Drezner ( 1980 ) suggested
that the facilities are circles of a given radius that cannot intersect but can be freely
located on the plane to minimize an expression similar to ( 13.1 )whered p.i/p.j/ is