Algoritmo Tabú para un problema de distribución de espacios // Tabu Search Algorithm for a Room Allocation Problem

Autores/as

  • Alfredo G. Hernández-Díaz Departamento de Economía, Métodos Cuantitativos e Historia Económica. Universidad Pablo de Olavide
  • Flor M. Guerrero Casas Departamento de Economía, Métodos Cuantitativos e Historia Económica. Universidad Pablo de Olavide
  • Rafael Caballero Fernández Departamento de Economía Aplicada (Matemáticas). Universidad de Málaga
  • Julián Molina Luque Departamento de Economía Aplicada (Matemáticas). Universidad de Málaga

Palabras clave:

Búsqueda tabú, problemas de asignación, tabu search, room allocation problems

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).

------------------------------------

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

Los datos de descargas todavía no están disponibles.

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.

Publicado

2016-11-04

Cómo citar

G. Hernández-Díaz, A., Guerrero Casas, F. M., Caballero Fernández, R., & Molina Luque, J. (2016). Algoritmo Tabú para un problema de distribución de espacios // Tabu Search Algorithm for a Room Allocation Problem. Revista De Métodos Cuantitativos Para La Economía Y La Empresa, 1, Páginas 25 a 37. Recuperado a partir de https://www.upo.es/revistas/index.php/RevMetCuant/article/view/2052

Número

Sección

Artículos