Modelo de clusterización de las instancias de optimización para la selección automática de parámetros de la heurística de optimización usada por la empresa SimpliRoute

Abstract

SimpliRoute es una StartUp con cinco años de experiencia en el mercado, la cual busca democratizar la resolución de los problemas de planificación de despacho que puede tener cualquier tipo de empresa. El producto principal que ha desarrollado, es una heurística de optimización que permite resolver el problema conocido como VRP (Vehicle Routing Problem). Este problema permite encontrar la ruta óptima que debe realizar una flota de vehículos para atender a sus clientes. El VRP es un problema con complejidad NP-Hard, lo que se traduce en que encontrar soluciones óptimas sea una tarea extremadamente difícil. En el contexto de la resolución del problema de ruteo de vehículos (VRP), el área de Data Science ha identificado que la heurística de optimización que actualmente es usada por SimpliRoute está siendo utilizado para resolver una gran variedad de problemas de planificación. Ahora bien, dado que la heurística de optimización no encuentra soluciones exactas sino que en base a reglas y criterios predefinidos encuentra soluciones que buscan acercarse al óptimo, es difícil pensar que la heurística pueda tener un buen desempeño al resolver para toda la variedad de instancias. Lo anterior se traduce en una problemática para la empresa, ya que la heurística actual no es capaz de encontrar las mejores soluciones para todos los casos, por lo que en este trabajo se plantea una solución que permita a la plataforma caracterizar el problema a resolver y a partir de dicha caracterización determinar aquella configuración de la heurística de optimización que genera que esta tenga el mejor desempeño para ese problema de planificación. Mencionado lo anterior, el objetivo general de este trabajo es generar un clasificador de instancias que entregue la mejor configuración de la heurística de optimización utilizado por SimpliRoute de modo de mejorar el desempeño del solver. Para abordar este objetivo, fue necesario definir una caracterización de las instancias y en base a esta se entrenaron diferentes modelos para realizar la predicción de la mejor configuración. De forma empírica, comparando dos configuraciones distintas, se encontraron casos en que la solución encontrada puede llegar a mejorar hasta en un 80%. En promedio, se puede llegar a mejorar la solución entre un 5-25 %. El modelo que escoge siempre la configuración con mejor desempeño logra una mejoría promedio de un 2:26%. Los resultados de este trabajo no fueron favorables, ya que no se obtuvo un modelo de predicción que resolviese la problemática. Sin embargo, se pudo reafirmar que la problemática planteada en este trabajo de título es relevante y merece la pena buscar otro enfoque para resolverlo, así como también se obtuvieron ideas importantes a considerar tanto para el funcionamiento de la heurística de optimización como para volver a abordar esta problemática, principalmente relacionado con el manejo de los datos.