Resumen de Asignación cuadrática (QAP) mediante Grasp

Quintín Martín Martín , Alvaro Morala Rodríguez

• 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.