Problema de ruteo del autobús escolar con recolección mixta

Abstract

En este trabajo se presenta una variante del "Problema de ruteo del autobús escolar" (SBRP) clásico, en el cual se trata de minimizar la distancia que se recorre en cada ruta. Concretamente el problema propuesto es una variante del problema de ruteo del autobús escolar para estudiantes con necesidades especiales, en el cual se considera la existencia de dos tipos de de estudiantes, con atributos diferentes al momento de decidir en donde se van a recoger, a diferencia de otras variantes existentes en la literatura, se considera la parte de asignación de los estudiantes como parte del problema ya que se considera que este parámetro influye al momento en que se crean las rutas, aun cuando la complejidad del problema se vea incrementada. La idea principal de este trabajo consiste en explorar tanto los métodos heurísticos como los exactos, para poder obtener una solución a la variante propuesta, ya sea de forma exacta o aproximada. De tal manera que se pueda identificar en qué casos conviene usar uno de estos métodos. El problema se modela como un programa lineal entero mixto, el cual posteriormente se resuelve mediate el software glpk y se encuentran soluciones para instancias pequeñas, que se toman como base para compararlas con las encontradas con el método heurístico utilizado. Para la parte heurística se optó por utilizar una de las técnicas clásicas: Un algoritmo glotón aleatorizado y adaptativo (GRASP, del inglés Greedy Randomized Adaptive Search Procedures), dado que se parte de la formulación matemática previamente obtenida para la parte exacta, fácilmente se puede adaptar para la elaboración del GRASP. La técnica GRASP es una meta-heurística muy rápida que genera soluciones de alta calidad, la cual se divide en dos fases: una de construcción de soluciones, que utiliza para ello un algoritmo glotón aleatorizado una fase de mejora, la cual realiza una búsqueda local. Este proceso se repite varias veces y la mejor solución encontrada se toma como el resultado, lo que al final nos proporciona una solución que, si bien no garantiza que sea la óptima, sí es de buena calidad y se puede obtener en un tiempo mucho menor en comparación con el tiempo que tarda encontrar la solución con un método exacto, cuando éste es capaz de encontrar una. Finalmente nos enfocamos en la versión más simple y general del problema para dar un algoritmo de aproximación, el cual se basa en un algoritmo que originalmente se diseñó para resolver una variante del problema de ruteo vehícular.