
Defensa Tesis Licenciatura Martín Mongi Badía
20 diciembre, 2019 @ 2:00 pm - 3:00 pm
Título: Algoritmos basados en programación lineal entera para el problema de ruteo de buses escolares
Director: Javier Marenco
Jurados: Dra. Paula Zabala y Dr. Federico Pousa
Resumen:
En esta tesis, estudiamos maneras de resolver el problema de ruteo de buses escolares. Este problema consiste en, dado un sector urbano, un conjunto de potenciales paradas, estudiantes y sus ubicaciones, buscar un conjunto de rutas y asignación de paradas óptimos. Aunque se pueden usar varias definiciones de optimalidad, nosotros buscamos minimizar la distancia recorrida por los buses. Nuestro enfoque es en la resolución exacta de este
problema.
Presentamos tres modelos diferentes de programación lineal entera básicos. Generamos variantes sobre los modelos particulares, con el fin de mejorar la performance. Con el objetivo de reducir la simetría de nuestros modelos, presentamos una técnica de agrupación de estudiantes. Creamos una heurística para utilizar una solución inicial y una heurística primal sobre subnodos. Realizamos una extensa experimentación y presentamos los resultados obtenidos y las conclusiones al respecto.