| Revue: | Computación y sistemas |
| Base de datos: | |
| Número de sistema: | 000560638 |
| ISSN: | 1405-5546 |
| Autores: | González Velázquez, Rogelio1 Granillo Martínez, Érika2 Bernabé Loranca, M. Beatriz1 Powell González, Jairo E.1 |
| Instituciones: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, México 2Benemérita Universidad Autónoma de Puebla, Facultad de Administración, México |
| Año: | 2022 |
| Periodo: | Ene-Mar |
| Volumen: | 26 |
| Número: | 1 |
| Paginación: | 271-279 |
| País: | México |
| Idioma: | Inglés |
| Resumen en inglés | 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. |
| Keyword: | Metaheuristics, GRASP, QAP, SQAP |
| Texte intégral: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
