Búsqueda tabú para resolver un problema de cambios de escuela en educación básica en México Distrito Federal

Abstract

Los métodos heurísticos son poderosas herramientas para abordar problemas cuyas soluciones de cómputo demandan grandes costos o que son computacionalmente intratables. El método heurístico “Búsqueda Tabú”, permite encontrar buenas soluciones a problemas de optimización combinatoria. En esta tesis, utilizando Búsqueda Tabú, se presenta una solución al problema de cambios de escuela de alumnos que no están de acuerdo con la secundaria asignada en la ciudad de México Distrito Federal. Este problema se modela como un sistema de programación entera binaria, donde a partir de 12,561 solicitudes de alumnos y 806 escuelas participantes, se da lugar a un gran sistema de optimización combinatoria de 12,561 variables binarias y 779 restricciones. // The heuristics methods are powerful tools to solve problems whose solutions require a lot of compute costs or are non-treatable in a computational way. The Tabu Search method achieves to find good solutions to combinatory optimization problems. In this thesis, Tabu Search method is used to solve the problem of changes of students, which do not agree with the assigned school in Mexico City. This problem is modeled as a binary integer programming system. This has to solve 12,561 school requests and 806 schools. With this information we build a binary integer programming system with 12,561 variables and 779 constrains.