Métodos de resolución eficientes para problemas de producción complejos : Aplicación a un problema de ruteo de vehículos

Abstract

En este informe se presenta el trabajo realizado sobre la aplicación de métodos heurísticos en problemas de programación lineal entera mixta. Se dio inicio al trabajo relevando y analizando la literatura relacionada, consultando más de 80 documentos sobre métodos heurísticos para la resolución de este tipo de problemas. En la elaboración del estado del arte se prestó principal interés en el funcionamiento de las heurísticas, además de la complejidad de los problemas, la calidad de los resultados y los tiempos de cómputo de los diferentes métodos. Se buscó la elección de métodos con buenos resultados y sencillos de implementar. Para poder evaluar los métodos seleccionados se decidió modelar un problema de ruteo de vehículos multi período. Específicamente, se tomó un problema real en donde se debe recoger los residuos valorizables generados en un mes por 54 empresas dentro del Parque Tecnológico Industrial del Cerro (PTIC), buscando minimizar la cantidad de distancia recorrida. Para la implementación del problema y de los métodos heurísticos propuestos se utilizó el lenguaje de modelado matemático GMPL, en conjunto con el paquete de optimización GLPK. Esta herramienta permitió aprovechar diversas funcionalidades para la formulación y resolución de problemas de optimización, tales como la definición de variables, restricciones y funciones objetivo, así como la ejecución de procedimientos iterativos personalizados. Además, con el objetivo de analizar el comportamiento de los métodos heurísticos, se incorporaron nuevas instancias mediante el uso de una biblioteca de casos de prueba. Estas instancias, de diferentes tamaños y características, permitieron una evaluación más amplia del desempeño de las heurísticas. Las heurísticas seleccionadas se dividen en dos objetivos, un método de búsqueda de solución inicial, Feasibility Pump (FP), y dos heurísticas de mejora de la solución, Objective Scaling Ensemble Approach (OSEA) y Local Branching (LB). Se crearon dos nuevos métodos de resolución heurísticos a través de la concatenación de ambos métodos, generando OSEA+LB y LB+OSEA como dos nuevos métodos de mejora. De los resultados obtenidos se determina que OSEA+LB es el método heurístico con mejores resultados, superando en algunas instancias a métodos de resolución GLPK. Para el problema de aplicación fue posible disminuir el valor obtenido de la función objetivo en la mitad de tiempo de cómputo comparado con la resolución a través de GLPK. Los dos métodos de mejora logran mejorar el resultado inicial y, en particular, la fortaleza de OSEA es la disminución en los tiempos de cómputo mientras que para LB es la calidad de la solución en términos de resultado obtenido. Además, se comparte la mejor solución obtenida para el problema de ruteo de vehículos del PTIC presentando un mapa con los recorridos propuestos. Se considera que el objetivo del proyecto fue alcanzado, logrando la elaboración de un documento estado del arte para los métodos heurísticos. Además, se logró la correcta implementación de tres heurísticas para la resolución de un problema real, alcanzando el mejor resultado mediante uno de estos métodos.