Tabu search algorithm for a room allocation problem
DOI:
https://doi.org/10.46661/revmetodoscuanteconempresa.2052Keywords:
Búsqueda tabú, problemas de asignación, tabu search, room allocation problemsAbstract
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).
Downloads
References
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, Nº 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.
Garey, M. y Johnson, D., 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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2006 Revista de Métodos Cuantitativos para la Economía y la Empresa
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Submission of manuscripts implies that the work described has not been published before (except in the form of an abstract or as part of thesis), that it is not under consideration for publication elsewhere and that, in case of acceptance, the authors agree to automatic transfer of the copyright to the Journal for its publication and dissemination. Authors retain the authors' right to use and share the article according to a personal or instutional use or scholarly sharing purposes; in addition, they retain patent, trademark and other intellectual property rights (including research data).
All the articles are published in the Journal under the Creative Commons license CC-BY-SA (Attribution-ShareAlike). It is allowed a commercial use of the work (always including the author attribution) and other derivative works, which must be released under the same license as the original work.
Up to Volume 21, this Journal has been licensing the articles under the Creative Commons license CC-BY-SA 3.0 ES. Starting from Volume 22, the Creative Commons license CC-BY-SA 4.0 is used.
