Algoritmos de aprendizaje reforzado para el problema de ruteo de vehículos dinámico

Abstract

En las formulaciones matemáticas más conocidas de los problemas de ruteo de vehículos es asumido que todos los clientes son conocidos desde un principio, permitiendo construir soluciones planificadas. Sin embargo, en situaciones más realistas suele suceder que algunos clientes sean conocidos después del periodo de planificación, cuando los vehículos ya están en sus rutas. Esto implica que la optimización tenga que hacerse en tiempo real para poder atender a aquellos clientes que lleguen de forma dinámica. Esta variación es conocida como el problema de ruteo de vehículos dinámico, el cual será estudiado en esta tesis. En este trabajo se propone abordar el problema desde el enfoque del aprendizaje de máquinas y los datos a través de algoritmos de aprendizaje reforzado. En esta clase de métodos, se modela el problema a través de un proceso de decisión de Markov, en el cual un agente busca maximizar una función de recompensas que va a depender de las acciones que tome en cada estado. Como primera opción se usan los algoritmos del tipo "Q-learning" y "Actor-Critic", ampliamente citados en el área. Por otro lado, se desarrolla un algoritmo que permite aprender a partir de simulaciones de escenarios, cuando se tiene información estocástica del medio. Se presentan una serie de experimentos computacionales para medir el desempeño de los modelos entrenados y se comparan con un algoritmo que utiliza una estrategia de "reoptimización" para tener una mejor apreciación de sus ventajas y desventajas.