quadratic assignment problem

A lot of real-world problems such as the assignment of special rooms in hospitals, operating room layout, image processing, etc., could be formulated in terms of Quadratic assignment problem. Different exact methods are suggested to solve these problems, but because of the special structure of these problems, by increasing the size of the problem, finding an exact solution become more complicated and even impossible. So, employing meta-heuristic algorithms is inevitable, due to this problem we use optics inspired optimization (OIO) in this paper. The obtained results and its comparison with the solutions of the central library of Quadratic assignment problem (QAPLIB) show that the proposed algorithm can exactly solve small-sized problems with 100% efficiency while the efficiency of medium-to-large size instances is 96%. Accordingly, one can conclude that the proposed OIO has generally high efficiency for solving permutation-based problems.

Construction Site Layout Planning (CSLP) is an important problem because of its impact on time, cost, productivity, and safety of the projects. In this paper, CSLP is formulated by the Quadratic Assignment Problem (QAP). At first, two case studies including equal and un-equal area facilities are solved by the simulated annealing optimization algorithm. Then, the obtained results are compared with the other papers. The comparisons show that the proposed Simulated Annealing (SA) is as efficient as ACO, PSO, CBO, ECBO, WOA, WOA-CBO, and ACO-PA which have been proposed by other papers for the same problems. As a result, the comparisons show that SA is as capable as other meta-heuristics of solving the combinatorial optimization problems like CSLP, while the hardware properties and computational times have been compared. Besides the comparisons, the design of experiments shows the relationship between each SA parameter and the computational time of the algorithm. Also, the history of convergence of the proposed SA indicates the high speed of reaching the optimal solution and the artificial intelligence of the proposed SA.

Quadratic assignment problem (QAP) is a well-known problem in the facility location and layout. It belongs to the NP-complete class. There are many heuristic and meta-heuristic methods, which are presented for QAP in the literature. In this paper, we applied 2-opt, greedy 2-opt, 3-opt, greedy 3-opt, and VNZ as heuristic methods and tabu search (TS), simulated annealing, and particle swarm optimization as meta-heuristic methods for the QAP. This research is dedicated to compare the relative percentage deviation of these solution qualities from the best known solution which is introduced in QAPLIB. Furthermore, a tuning method is applied for meta-heuristic parameters. Results indicate that TS is the best in 31% of QAPs, and the IFLS method, which is in the literature, is the best in 58 % of QAPs; these two methods are the same in 11% of test problems. Also, TS has a better computational time among heuristic and meta-heuristic methods.

Assigning facilities to locations is one of the important problems, which significantly is influence in transportation cost reduction. In this study, we solve quadratic assignment problem (QAP), using a meta-heuristic algorithm with deterministic tasks and equality in facilities and location number. It should be noted that any facility must be assign to only one location. In this paper, first of all, we have been described exact methods and heuristics, which are able to solve QAP; then we have been applied a meta-heuristic algorithm for it. QAP is a difficult problem and is in NP-hard class, so we have been used honey bee mating optimization (HBMO) algorithm to solve it.This method is new and have been applied and improved NP-hard problems. It’s a hybrid algorithm from Honey-Bee Mating system, simulated annealing and genetic algorithm.