Algoritmo Tabú para un problema de distribución de espacios
DOI:
https://doi.org/10.46661/revmetodoscuanteconempresa.2052Palabras clave:
Búsqueda tabú, problemas de asignación, tabu search, room allocation problemsResumen
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).
------------------------------------
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).
Descargas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2006 Revista de Métodos Cuantitativos para la Economía y la Empresa
Esta obra está bajo una licencia internacional Creative Commons Atribución-CompartirIgual 4.0.
El envío de un manuscrito a la Revista supone que el trabajo no ha sido publicado anteriormente (excepto en la forma de un abstract o como parte de una tesis), que no está bajo consideración para su publicación en ninguna otra revista o editorial y que, en caso de aceptación, los autores están conforme con la transferencia automática del copyright a la Revista para su publicación y difusión. Los autores retendrán los derechos de autor para usar y compartir su artículo con un uso personal, institucional o con fines docentes; igualmente retiene los derechos de patente, de marca registrada (en caso de que sean aplicables) o derechos morales de autor (incluyendo los datos de investigación).
Los artículos publicados en la Revista están sujetos a la licencia Creative Commons CC-BY-SA de tipo Reconocimiento-CompartirIgual. Se permite el uso comercial de la obra, reconociendo su autoría, y de las posibles obras derivadas, la distribución de las cuales se debe hacer con una licencia igual a la que regula la obra original.
Hasta el volumen 21 se ha estado empleando la versión de licencia CC-BY-SA 3.0 ES y se ha comenzado a usar la versión CC-BY-SA 4.0 desde el volumen 22.
