Reactive Search: Quadratic Assignment

Contact us to buy or request information

The Quadratic Assignment Problem (QAP) models the real-world task of finding the optimal location for a set of interdependent facilities to minimize the cost of moving commodities between them.

A set of n facilities and a set of n locations are given; a distance is specified for each pair of locations and a weight or flow is given for every pair of facilities. Such weight represents the amount of supplies to be transported. The request is to assign all facilities to different locations with the goal of minimizing the total cost of moving supplies between facilities; the cost is given by the sum of the distances multiplied by the corresponding flows.

In mathematical terms, the problem data are:

• the number n of facilities and locations;
• distance(i, j) between locations i and j
• weight(i, j) describing the flow between facilities i and j.

Note that the number of locations is equal to the number of facilities, so that the problem's outcome must be a permutation (loc[1], . . . , loc[n]) where loc[i] is the chosen location of facility i. The objective function to minimize is

More details in the user manual.

Contact us to buy or request information