Algoritmo Tabú para un problema de distribución de espacios
- Hernández-Díaz, Alfredo G.
- Guerrero Casas, Flor María
- Caballero Fernández, Rafael
- Molina Luque, Julián
ISSN: 1886-516X
Ano de publicación: 2006
Volume: 1
Páxinas: 25-37
Tipo: Artigo
Outras publicacións en: Revista de métodos cuantitativos para la economía y la empresa
Resumo
The distribution of spaces is a usual real problem presented when we have to assign simultaneously different sets of spaces (offices, rooms, halls, etc.). These spaces are distributed in buildings and/or floors and have to be assigned among several groups of people. The aim is to minimize the total distance among the spaces assigned to each group and its head office. This situation drives us to a quadratic combinatorial problem, so difficult to solve with exact methods. This is the reason to propose a metaheuristic method to solve it, a Tabu Search algorithm with two types of movements: the swapping of two offices and further assignment of head offices. The performance of the algorithm is demonstrated on a problem related with the Pablo de Olavide University in Seville (Spain).
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.