Asignación cuadrática (QAP) mediante Grasp

  1. Martín Martín, Quintín
  2. Morala Rodríguez, Alvaro
Buch:
XXVI Congreso Nacional de Estadística e Investigación Operativa: Úbeda, 6-9 de noviembre de 2001

Verlag: Jaén : Universidad de Jaén, 2001

ISBN: 84-8439-080-2

Datum der Publikation: 2001

Kongress: Congreso Nacional de Estadística e Investigación Operativa (26. 2001. Úbeda)

Art: Konferenz-Beitrag

Zusammenfassung

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.