Abstract:
The Quadratic assignment problem (QAP) is one of the most interesting and most
challenging combinatorial optimization problems in existence. Assigning facilities to
locations is a common application of the quadratic assignment problem. Most previous
studies in this direction have only dealt with deterministic assignment problem, which
assumes that all the problem parameters are known with certainty. However, in general,
plants, distribution centers, and other facilities generally function for years or decades,
during which time the environment in which they operate may change substantially.
Costs, demands, travel times, and other inputs to classical facility location models may be
highly uncertain. There exist a few studies that deal with quadratic assignment problem
under aleatory uncertainty (i.e., natural or physical variability), which assume that point
data are available for the problem parameters. However, in some cases, it is likely that the
problem parameters are available only as upper and lower bounds (i.e., intervals). This has
made the development of models for facility location under interval uncertainty a high
priority for researchers and the objective of the present study is to formulate a
methodology for solving a probabilistic quadratic assignment problem under interval
uncertainty.
Specifically, the study accomplishes this objective through: (1) Development of a
formulation for QAP under interval uncertainty and (2) Development of a probabilistic
framework for solving the formulation for QAP under interval uncertainty.
The methodology developed in this research is illustrated through problem related to
assignment of facilities to locations considering uncertain distances and workflows.