Análise de heurísticas para o problema da alocação quadrática

Abstract

The QAPis a classic combinatorial optimization problem that seeks to minimize the total cost of allocating n facilities in n locations. Each location must receive exactly one facility, considering both the distance between points and the flow between facilities. The QAP is used in various real-world applications, such as room allocation in hospitals and component allocation in an electronic circuit. This work focuses on comparing different heuristics applied to solving the problem. It is an empirical research, based on the implementation and experimentation of the ant colony heuristic and ES-VND for solving the QAP. These solutions mentioned are already presented in the literature, so a comparative study of these solutions is sought. As an additional contribution, the heuristic called ES-SA is also proposed, a mixed solution between the Evolutionary algorithm and Simulated recognition. Based on ES-VND but changing the local search mechanism used. Following the implementations, a comparative analysis was performed between the methods, using different instances of the problem extracted from the QAPLIB library—a repository recognized in the literature, which brings together more than 130 distinct instances of the PAQ. In this way, the aim is to contribute to the empirical and in-depth evaluation of the different heuristic strategies applied to the PAQ, through the use of quantitative metrics in the results. The heuristics developed in this work showed better results than the Ant Colony Optimization in some instances, with the Ant Colony having the worst result and the ES-SA obtaining the best.