Developing an Effective Decomposition-Based Procedure for Solving the Quadratic Assignment Problem

摘要

The quadratic assignment problem is involved with designing the best layouts for facilities and has a wide variety of applications in industry. This paper presents a decomposition-based procedure for solving this NP-hard optimization problem. The procedure aims at enhancing an initial solution in five interacting and synergetic layers. In the first layer, the initial solution undergoes the process of local search and becomes local optimal. In the second layer, the linear assignment technique is called and results in a suggestion for an enhancement. The third layer is about decomposing the proposed suggestion into several cycles. Then, in the fourth layer, each cycle is further decomposed into several segments. The number of the segments associated with each cycle is the length of the corresponding cycle, which was calculated in the third layer. Finally, the segments are processed in the fifth layer and potentially enhance the original solution. The employed decomposition has proved to be effective, and comparing the performance of the procedure with that of other state-of-the-art procedures indicates its efficiency.