SOLVING QUADRATIC ASSIGNMENT PROBLEM USING FORWARD AND BACKWARD EXCHANGE ALGORITHM

Quadratic assignment problem is one of the combinatorial optimization problems of deciding the placement of facilities in specified locations in such a way as to minimize a nonconvex objective function expressed in terms of flow between facilities, and distance between location. Since QAP is NP-hard problem, and even finding an ε-approximate solution is a difficult problem, therefore to get a ‘good’ starting point is necessary, in order to obtain a better optimal solution. In this paper we propose a random point strategy to get initial starting point and then use forward exchange algorithm and backward exchange algorithm to get ‘optimal’ solution. As a computational experience we solved the problem of Had12, Esc 16b, Esc 16c and Esc 16h from QAPLIB. Finally, we present a comparative study between our proposed algorithm and Data –Guided Lexisearch Algorithm. The computational study shows the effectiveness of our proposed algorithm.