Optimización de la planificación de servicios - Sánchez Yepez, Gabriela (2019)
Objetivos y método de estudio: El principal objetivo de esta tesis es estudiar un problema de planificación de servicios de telecomunicaciones que consiste en asignar órdenes de servicio a un conjunto de cuadrillas disponibles, así como en determinar la secuencia en que deben realizarse dichos servicios, con el fin de balancear el salario de las cuadrillas. El estudio busca desarrollar modelos matemáticos y algoritmos de solución para al menos una variante del problema de planificación de servicios, con el fin de contribuir al avance del estado del arte en las áreas de ruteo de vehículos, logística y transporte. La metodología de investigación que se siguió para lograr los objetivos propuestos es la siguiente: Revisión del estado del arte de problemas de ruteo de vehículos con beneficios, con enfásis en el Team Orienteering Problem. Formulación matemática del problema de estudio. Fueron propuestas dos formulaciones. Adaptación de las instancias propuestas por Chao et al. (1996b). Validación del alcance de los modelos matemáticos propuestos, mediante la solución de las instancias haciendo uso del optimizador CPLEX 12.8. Comparación de los modelos propuestos. Implementación del algoritmo metaheurístico tipo GRASP (Procedimiento de búsqueda voraz aleatorizado y adaptativo) reactivo. Experimentación computacional de los algoritmos propuestos. Análisis de resultados. Contribuciones y conlusiones: Se proponen dos formulaciones matemáticas para el problema de estudio cuya diferencia radica en la forma que se aborda el balanceo del salario de las cuadrillas. En la primer formulación (Max-Min), se maximiza el mínimo de los salarios de las cuadrillas y en la segunda (Min-Max), se minimiza la máxima de las desviaciones con respecto al salario promedio. Los modelos se basan en la formulación del Team Orienteering Problem considerando restricciones adicionales, tales como la compatibilidad entre los servicios solicitados y las cuadrillas. La validación de las formulaciones propuestas se realiza resolviendo un gran conjunto de instancias, con el Branch and Bound del optimizador CPLEX 12.8. Los resultados permiten evaluar el desempeño de una metaheurística GRASP reactiva, propuesta como alternativa de solución al problema. El GRASP reactivo logra obtener soluciones de buena calidad en tiempos de cómputo aceptables, resolviendo a optimalidad 161 de las 185 instancias reportadas por el optimizador en el modelo Max-Min y 159 de las 189 reportadas en el modelo Min-Max. Además, logra mejorar los resultados obtenidos con el optimizador en 112 instancias en el primer modelo y 121 en el segundo, lo que equivale a cerca de un tercio del total de las instancias.