Name
Abstract | ||
|---|---|---|
In the generalized quadratic assignment problem (GQAP) we are given n weighted facilities, m capacitated sites, a traffic intensity matrix between facilities, a distance matrix between sites, unit traffic costs, and assignment costs of facilities to sites. The aim is to determine an assignment of facilities to sites so that the sum of assignment and traffic costs is minimized and the total weight of all facilities assigned to the same site does not exceed the site capacity. The GQAP is a generalization of the quadratic assignment problem (QAP) in which n = m and exactly one facility must be assigned to each site. The problem has applications in container yard management and in the assignment of equipment to manufacturing sites. This article describes a memetic heuristic for the GQAP, as well as an integer linear programming formulation that can be solved by CPLEX for small instances. For larger instances, feasible solutions can be obtained by a truncated branch-and-bound procedure. Computational experiments show that on small instances the proposed heuristic always yields an optimal solution; on larger instances it always outperforms the truncated branch-and-bound algorithm. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1287/ijoc.1040.0128 | INFORMS Journal on Computing |
Keywords | Field | DocType |
larger instance,traffic intensity matrix,generalized quadratic assignment problem,site capacity,small instance,memetic heuristic,unit traffic cost,assignment cost,traffic cost,m capacitated site,quadratic assignment problem,genetic algorithm,tabu search | Weapon target assignment problem,Mathematical optimization,Heuristic,Quadratic assignment problem,Generalized assignment problem,Traffic intensity,Assignment problem,Mathematics,Tabu search,Linear bottleneck assignment problem | Journal |
Volume | Issue | ISSN |
18 | 4 | 1091-9856 |
Citations | PageRank | References |
16 | 0.82 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-François Cordeau | 1 | 2604 | 127.77 |
| Manlio Gaudioso | 2 | 207 | 23.95 |
| Gilbert Laporte | 3 | 8666 | 612.13 |
| Luigi Moccia | 4 | 192 | 11.25 |