Development of a methodology for probabilistic quadratic assignment problem(QAP) under interval uncertainty

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.