Robust quadratic assignment problem with budgeted uncertain flows

摘要

We consider a generalization of the classical quadratic assignment problem, where material flows between facilities are uncertain, and belong to a budgeted uncertainty set. The objective is to find a robust solution under all possible scenarios in the given uncertainty set. We present an exact quadratic formulation as a robust counterpart and develop an equivalent mixed integer programming model for it. To solve the proposed model for large-scale instances, we also develop two different heuristics based on 2-Opt local search and tabu search algorithms. We discuss performance of these methods and the quality of robust solutions through extensive computational experiments. Highlights ? A robust approach for quadratic assignment problem (RQAP) with budgeted uncertainty. ? An exact and two heuristic methods to solve RQAP. ? Extensive experiments to show performance of methods and quality of solutions. ? RQAP can be solved significantly faster than minmax regret QAP. ? RQAP has adjustable conservativeness while minmax regret QAP has not.