Desarrollo de una red neuronal entrenada con aprendizaje reforzado aplicada al problema de ruteo de una flota de vehículos eléctricos

Abstract

El problema de ruteo de vehículos (VRP, por su sigla en inglés) consiste en un problema de optimización combinatorial que busca encontrar la respuesta a la pregunta: “¿Cuál es el conjunto óptimo de rutas para una flota que debe satisfacer las demandas de un conjunto dado de clientes?”. Existen tres elementos principales involucrados en el VRP, que son: los clientes, la bodega o depósito del cual se extraen los productos y la flota, que puede considerar 1 o más vehículos. En los problemas reales de VRP, se aplican diversas restricciones, entre las que destacan: capacidad limitada de los vehículos, varios puntos de suministro (múltiples depósitos) y los clientes deben ser visitados en una ventana de tiempo determinada. La importancia de la solución a este problema radica en los significativos ahorros relacionados al costo de transporte y despacho de productos que pueden significar hasta el 10% del costo total[1]. En el presente trabajo, se realizó una investigación bibliográfica sobre las soluciones del VRP propuestas en la literatura. Estas propuestas son explicadas y analizadas para entender posteriormente las soluciones desarrolladas en este trabajo. Además, se realizó una investigación sobre el algoritmo de aprendizaje reforzado y su aplicación en redes neuronales para el VRP. A raíz de lo anterior, la instancia del VRP abordada en este trabajo, consiste en una flota de 3 vehículos eléctricos que deben satisfacer la demanda en los destinos, considerando las siguientes restricciones: pausas de reabastecimiento de batería para mantener el estado de carga (SoC, por su sigla en inglés) entre ciertos límites, capacidad limitada del vehículo y número máximo de pausas de reabastecimiento. En este trabajo se desarrollaron tres soluciones basadas en redes neuronales, que atacan el problema de distintos enfoques. La primera solución corresponde a una red neuronal que considera cargas completas de batería en cada pausa de reabastecimiento. El segundo modelo consiste en un modelo con estaciones de carga ficticias con distintos porcentajes de carga. Por último, la tercera solución hace uso de una red neuronal adicional con salida continua, la cual es interpretada como el porcentaje a cargar en las pausas de reabastecimiento. Las tres redes neuronales fueron programadas en Python utilizando principalmente la librería Pytorch, la cual está optimizada para la implementación y entrenamiento de redes neuronales profundas. A partir de resultados obtenidos en este trabajo, se concluye la correcta implementación tanto de las redes neuronales, como del algoritmo de entrenamiento reforzado. Además, en términos de desempeño general, se concluye que el mejor rendimiento lo obtiene el modelo de carga continua, seguido por el modelo de carga completa y por último el modelo de estaciones de carga ficticias.