Algoritmo Tabú para un problema de distribución de espacios

  1. Hernández-Díaz, Alfredo G.
  2. Guerrero Casas, Flor María
  3. Caballero Fernández, Rafael
  4. Molina Luque, Julián
Revista:
Revista de métodos cuantitativos para la economía y la empresa

ISSN: 1886-516X

Año de publicación: 2006

Volumen: 1

Páginas: 25-37

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openRIO editor

Otras publicaciones en: Revista de métodos cuantitativos para la economía y la empresa

Resumen

La distribución de espacios es un problema que habitualmente se presenta en situaciones reales cuando se deben asignar simultáneamente diferentes conjuntos de espacios (despachos, habitaciones, salas, etc.) distribuidos entre edificios y/o plantas entre varios grupos de personas de tal forma que se minimicen las distancias entre los espacios asignados a cada grupo y la sede de dicho grupo. Esta situación da lugar a un problema combinatorio con una función objetivo cuadrática, lo cual complica enormemente su resoluci ón mediante un método exacto. Por este motivo, proponemos para su resolución un metaheurístico basado en Búsqueda Tabú con dos grupos de movimientos claramente diferenciados: intercambio de despachos y reasignación de sedes. Finalmente, aplicamos dicho algoritmo a un caso real en la Universidad Pablo de Olavide de Sevilla (España).

Referencias bibliográficas

  • Burke, E. y Carter, M., Practice and Theory of Automated Timetabling, Vol. II, Selected Papers of the First International Conference, Edinburgh, UK, Ed. Springer, 1998.
  • Carter, M., A Langangian Relaxation Approach to the Classroom Assignment Problem, INFOR, 27, No 2, 1989.
  • Ciriani, V., Pisanti, N. y Bernasconi, A., Room allocation: a polynomial subcase of the quadratic assignment problem, Discrete Applied Mathematics, 144, pp. 263-269, 2004.
  • Díaz, J. A. y Fernández, E., A Tabu search heuristic for the generalized assignment problem, European Journal of Operational Research, 132, pp. 22-38, 2001.
  • Gandibleux, X., Morita, H. y Katoh, N., Use of a genetic heritage for solving the assignment problem with two objectives. En Evolutionary Multi-Criterion Optimization (C. Fonseca, P. Fleming, E. Zitzler, K. Deb, L. Thiele Eds.). EMO 2003, Second International Conference, Faro, Portugal, April 2003 Proceedings. Lecture Notes in Computer Sciences 2632, pp. 43-57, Springer.
  • Gandibleux, X., Morita, H. y Katoh, N., A population-based metaheuristic for solving assignment problems with two objectives, in Journal of Mathematical Modelling and Algorithms, por aparecer.
  • M. Garey y D. Johnson, Computers and Intractability. New York: Freeman, 1979.
  • Glover, F., Future Paths for Integer Programming and links to artificial intelligence, Computers & Operational Research, 5, pp. 533-549, 1986.
  • Glover, F. y Laguna, M., Tabu Search, Kluwer Academic Publishers, Boston, 1997.
  • Herault, L. y Privault, C., Solving a Real World Assignment Problem with a Metaheuristic, Journal of Heuristics, 4, pp. 383-398, 1998.
  • Kelly, J. P., Laguna, M. y Glover, F., A Study on Diversification Strategies for the Quadratic Assignment Problem, Computers and Operations Research, 21, no. 8, pp. 885-893, 1994.
  • Laguna, M., Kelly, J. P., González Velarde, J. L. y Glover, F., Tabu Search for the Multilevel Generalized Assignment Problem, European Journal of Operational Research, 82, pp. 176-189, 1995.
  • López García, L., Pérez de la Torre, L., Rodríguez Romano, N. y Posada Bolívar, A., El problema de asignación de salones: solución con la heurística Búsqueda Tabú, Actas del 2° Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB), Gijón, 2003.
  • Middendorf, M., Freischle, F. y Schmeck, H., Multi Colony Ant Algorithms, Journal of Heuristics, 8, pp. 305-320, 2002.
  • Osorio, M.A. y Laguna, M., Logic Cuts for Multilevel Generalized Assignment Problems, European Journal of Operational Research, 151, pp. 238-246, 2003.
  • Yagiura, M., Iwasaki, S., Ibaraki, T. y Glover, F., A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Discrete Optimization, 1, pp. 87-98, 2004.
  • Wang, Y.-Z., An application of genetic algorithm methods for teacher assignment problem, Expert Systems with Applications, 22, pp. 295-302, 2002.
Fuente de los datos: Dialnet