A Neighborhood Combining Approach in GRASP's Local Search for Quadratic Assignment Problem Solutions

Autores/as

  • Erika Granillo Martinez Benemerita Universidad Autonoma de Puebla
  • Rogelio González Velázquez
  • María Beatriz Bernabé Loranca
  • José Luis Martínez Flores

DOI:

https://doi.org/10.13053/cys-22-1-2779

Palabras clave:

Meta-heuristics, NP-hard, neighborhood structure, combinatorial optimization, local search, GRASP, QAP

Resumen

In this paper we describe a study for the search of solutions of the combinatorial optimization problem Quadratic Assignment Problem (QAP) through the implementation of a Greedy Randomized Adaptive Procedure Search (GRASP) and have been compared with the best solutions known in the literature, obtaining robust results in terms of the value of the objective function and the execution time. Also a comparison with the ant algorithm is presented with the aim of comparing the meta-heuristic. The most important contribution of this paper is the use of the combination of different neighborhood structures in the GRASP improvement phase. The experiment was performed for a set of test instances available in QAPLIB. The QAP belongs to the Np-hard class whereby this approximation algorithm is implemented.

Biografía del autor/a

Erika Granillo Martinez, Benemerita Universidad Autonoma de Puebla

Profesor de la facultad de Administración de la BAUPCandidata a Doctor en Logìstica y la Dirección de la Cadena de SuministroDos publicacionesPremio por mejor publicación en congreso internacionalConsultor empresarial 

Descargas

Archivos adicionales

Publicado

2018-03-30

Número

Vol. 22 Núm. 1 (2018): Thematic Issue on Language & Knowledge Engineering (Guest Editors: D. Pinto, D. Vilariño, B. Beltrán)

Sección

Articles of the Thematic Issue

Licencia

Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.

Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.

El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.

Esta Transferencia está sujeta a las siguientes reservas:

  • Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
  • Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.