Simulated Annealing Algorithm for the Quadratic Assignment Problem

Quadratic Assignment Problem - QAP

Problema Alocarii Patratice sau QAP este una din problemele cele mai cunoscute si mai complicate in problemele de optimizare combinationala care au fost propuse de Koopmans si Beckmann in 1957. In 1976, Sahni si Gonzales au aratat ca QAP apartine clasei de probleme NP-hard (non-deterministic polynomial-time hard). QAP a fost luata in considerare de multi cercetatori pentru mult timp si este capabila sa modeleze multe probleme reale din viata de zi cu zi.

In QAP, mai multe facilitati (de exemplu, n fabrici) sunt alocate in mai multe locatii (de exemplu, n orasele) in asa fel incat distanta intre oricare dintre locatii si, de asemenea, fluxul intre oricare dintre facilitati, sunt constante si predeterminate. Aceasta atribuire ar trebui sa fie intr-un mod in care scopul functiei, care este afectata de distanta dintre locatii si numarul de circulatii a bunurilor intre facilitati, sa fie minimizata. In general cand scopul este de a aloca n facilitati la n locatii, numarul de situatii posibile este n!. De aceea aceasta problema face parte din categoria NP-completa.

In definitia matematica a QAP, exista n locatii cu coordonate specifice. Deci, o matrice nxn reprezinta distanta dintre fiecare pereche de locatii ce vor fi generate

( D = [dij]nxn). Cealalta matrice generata nxn include fluxul fiecarei perechi de facilitati

( F = [fij]nxn) . Avand in vedere distanta dintre locatii si fluxul dintre facilitati, obiectivul este de a gasi costul minim pentru atribuirea facilitatilor. Matematic, daca S(n) se presupune a fi un set a tuturor permutarilor posibile pentru un set de {0,1, ..., n}, scopul este de a gasi o permutare cum ar fi p ? S (n) , care sa fie capabila sa minimizeze o functie cost definita ca in ecuatia :

De fapt, permutarea p prezinta secventa de plasamente a facilitatilor in locatii.

O descriere mai este aratata in urmatoarea figura:

In aceasta figura se decide sa se plaseze 4 elemente electronice in 4 locatii specifice. Matricea D reprezinta distanta dintre fiecare pereche de locatii si Matricea F reprezinta numarul de conexiuni necesare intre cele doua parti.

Asa cum se arata in Figura 1, considerand lungimea firelor consumate, rezultatul optim este obtinut cand elementul #3 este palsat in locatia #1, elementul #1 in locatia #2, elementul #4 in locatia #3 si elemetul #2 in locatia #4.