Asignación cuadrática (QAP) mediante Grasp

• Autores: Quintín Martín Martín , Alvaro Morala Rodríguez
• Localización: XXVI Congreso Nacional de Estadística e Investigación Operativa: Úbeda, 6-9 de noviembre de 2001, 2001, ISBN 84-8439-080-2
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • En este trabajo se estudia el problema de asignación cuadrática (QAP), en el cual se desea encontrar la mejor asignación de n instalaciones a n localizaciones dadas, problema clásico dentro de los problemas de optimización combinatoria.

    En el algoritmo GRASP que vamos a utilizar se definen dos matrices (D y F) que pueden ser o no simétricas y con valores iguales o distintos de cero en las diagonales principales. Para medir el coste de cada posible asignación (hay n! de ellas) multiplicamos el flujo prescrito entre cada una de las instalaciones por la distancia entre sus localizaciones asignadas, y sumamos todos los pares. Nuestro deseo es encontrar la asignación, mediante GRASP, que minimice ese coste.