GRASP Proposal for the Search for SQAP Solutions

Abstract

The Quadratic Assignment Problem (QAP) consists of finding an optimal allocation of n facilities to n locations in such a way as to minimize the cost of interaction between facilities. The QAP is considered as a NP-hard. This article presents an application of QAP that consists of modeling a traffic system by introducing a probability transition matrix to transform the QAP into the Stochastic Quadratic Assignment Problem (SQAP). The objective of this article is to find solutions for SQAP through the implementation of the metaheuristic Greedy Randomized Adaptive Search Procedure (GRASP), in the JAVA programming language. The program is executed for a set of test instances and the results obtained by the application of two search strategies that make four combinations in the construction phases and the post processing phases of the metaheuristics. The program was also executed for a problem that presents instances of size n = 12 to 30, whose optimal solution is given. Given the need to offer solutions to logistics problems of the NP-hard class, a tool for approximating the optimal solutions is presented.