Algoritmo guloso adaptativo e aleatório para o problema quadrático de alocação

Rangel, Maria Cristina; Abreu, Nair Maria M. de; Boaventura-Netto, Paulo Oswaldo

doi:10.1590/S0103-65131999000200003

Article

Algoritmo guloso adaptativo e aleatório para o problema quadrático de alocação

Rangel, Maria Cristina; Abreu, Nair Maria M. de; Boaventura-Netto, Paulo Oswaldo

http://dx.doi.org/10.1590/S0103-65131999000200003 Prod, vol.9, n2, p.37-48, 1999

PDF

Downloads: 0

Resumo

O Problema Quadrático de Alocação (PQA) pertence à classe dos problemas NP-hard. Apesar de muitos métodos heurísticos terem sido desenvolvidos visando a resolução de suas instâncias, ainda não é possível encontrar soluções ótimas para instâncias de ordem acima de 25- Uma versão do GRASP, desenvolvida por Li, Pardalos e Resende [LPR94], se mostrou bastante eficiente para o PQA, o que motivou os autores a elaborar uma proposta de modificação na sua busca local, na tentativa de diminuir o número de iterações necessário à obtenção da melhor solução conhecida.

Palavras-chave

Otimização Combinatória, Meta-heurística, Problema Quadrático de Alocação

Abstract

The Quadratic Assignment Problem (QAP) is an NP-hard problem. Despite the continuous effort in the formulation of new heuristics, optimal solutions are not generally known yet, for instances of order n > 25. A GRASP-type heuristic developed by Li, Pardalos and Resende [LPR94] showed itself to be very efficient and this fact motivated the authors to propose a perfectioning in its local search reducing the number of iterations.

Keywords

Combinatorial Optimization, Metaheuristic, Quadratic Assignment Problem

References

[Ab84] Abreu, N.M.M., "Um estudo algébrico e combinatório do problema quadrático de alocação segundo Koopmans e Beckmann ", (1984), Tese de Doutorado, COPPE/UFRJ.

[AQB99] Abreu, N.M.M , Querido, T.M., e Boaventura-Netto, RO., "Redlnv-SA: a simulated annealing for the quadratic assignment problem", RAIRO Oper. Res. 33 (1999),249-273.

[Bo87] Bokari, S.H., "Assignment problems in parallel and distributed computing", Kluwer Academic Publishers, Boston, 1987.

[BKR97J Burkard, R.E., Karisch, S.E. e Rendl, F., "QAPLIB - A Quadratic Assignment Problem Library", Journal of Optimization, 10 (1997), 391-403. Internet address: http://opt.math.tu-graz.ac.at/~karisch/qaplib/

[DH72] Dickey, J.W. e Hopkins, J.W., "Campus building arrangement using TOPAZ", Transportation Research, 6, (1972), 59-68.

[DMM97] M. Dell' Amico, F. Maffioli and S. Martello, "Annotated bibliographies in combinatorial optimization", Jonh Wiley & Sons, Chichester (1997)

[El77] Elshafei, A,N, "Hospital layout as a quadratic assignment problem ", Operations Research Quaterly, 28, (1977), 55-86.

[FF94] Fleurent C. and Ferlad, "Genetic Hybrids for the QAPs", in quadratic assignment and related problems, P. Pardalos and Wolkowicz, eds. DIMACS 16 (1994), 173-187, AMS.

[GG76] Geoffrion, A.M. e Graves, G.W., "Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment problem/LP approach ", Op. Res. 24(1976), 595-610.

[Glo89a] Glover, R, "Tabu search - Part I", ORSAJ. Comp. 1 (1989), 190-206.

[Glo89b] Glover, F., "Tabu search - Part II" ORSA J. Comp. 2 (1989), 4-32.

[GP66] Gavett, J.W. e Plyter, N.V., "The optimal assignment of facilities to locations by branch-and-bound', Op. Res. 14 (1966), 53-76.

[GTD97] Gambardella, L.M., Taillard, E.D. e Dorigo, M., "Ant colonies for the QAP", Technical Report IDSIA 97-4, IDSA, Switzerland (1997).

[GW89] Grötschel, M. e Wakabayashi, "A cutting plane algorithm for a clustering problem", Mathematical Programming, 45, (1989), 59-96.

[Hf77] Heffey, D.R., "Assignment runners to a relay team" in Optimal Strategies in Sports S.P. Ladany and R.E. Macholeds, Noth - Holland, Amsterdam, (1977), 260-171.

[HLP52] Hardy, G.H., Littlewood, J.E. e Pólya, G., "Inequalities ", Cambridge University Press, Cambridge, 1954.

[Hu87] Hubert, L.J., "Assignment method in combinatorial data analysis ", Marcel Dekker, Inc, New York, NY 10016 (1987).

[JMRW94] Jünger, M., Martin, A., Reinelt, G. e Weissmantel, R., "Quadratic 0-1 optimization and a decomposition approach for the placement of eletronic circuits", Mathematical Programming, 63, (1994), 257-279.

[KB57] T. C. Koopmans and M. Beckmann, "Assignment Problems and the Location of Economic Activities", Econometrica, (1957), 25, no. 1, pp. 53-76.

[KP78] Krarup, J. e Pruzan, P.M., "Computed-aided layout design", Mathematical Programming Study, 9, (1978), 75-94.

[LM88] Laporte, G. e Mercure, H., "Balancing hydraulic turbine runners: a quadratic assignment problem ", EJOR, 35, (1988), 378-382.

[LPR94] Li,Y., Pardalos, P.M. e Resende, M.G.C., "A greedy randomized adaptive search procedures for the quadratic assignment problem ", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16 (1994), 237-261.

[MCD94] Maniezzo, V., Colorni, A. e Dorigo, M., "The ant system applied to the quadratic assignment problem", Technical Report 94/28, IRIDIA, Université Libre de Bruxelles (1994)

[MP97] Mavridou, T. e Pardalos P.M., "Simulated annealing and genetic algorithms for the facility layout problem: a survey", Computational Optmization and Applications, 7, (1997), 111-126.

[Sk90] Skorin-Kapov, J., "Tabu search applied to the quadratic assignment problem ", ORSA J. Comp. 2 (1990), nº1, 33-45.

[St61] Steinberg, L., "The blackboard wiring problem: a placement algorithm ", SIAM Review, 3, (1961), 37-50.

[Ta91] Taillard, E., "Robust Taboo Search for the quadratic assignment problem ", Parallel Comput., 1991, 17, 4-5, pp. 443-455.

[TS95] Tate, D.M. e Smith, A. E., "A genetic approach to the quadratic assignment problem ", Computers and Operations Research, 22,(1995), 73-83.

[Wi87] Wilhelm, M.R. e Ward, T.L., "Solving quadratic assignment problem by simulated annealing ", IEEE Trans. 19 (1987) nº1, 107-119.

[Wi58] Wimmert, R.J., "A mathematical model of equipment location", J.J.E. (1958), 9, 6, 498-505.

Algoritmo guloso adaptativo e aleatório para o problema quadrático de alocação