Solución del problema de ruteo de vehículos capacitado (cvrp) usando el algoritmo de aprendizaje reforzado q-learning.

Abstract

El propósito de la siguiente investigación es dar solución a instancias de la literatura para el problema de ruteo de vehículos capacitado (CVRP) según formulación VRP4 de Toth & Vigo (2002) por medio de un algoritmo de aprendizaje reforzado conocido como Q-Learning. El desarrollo del algoritmo se realizó en Python y utiliza parámetros como tasa de aprendizaje, factor de descuento y factor de descomposición, cuya incidencia en la función objetivo del CVRP es evaluada a través de un diseño factorial 2^k. Se realizó en una revisión de literatura donde se encontró que el VRP ha sido ampliamente estudiado desde 1959 a través métodos exactos, heurísticos y metaheurísticos, que ofrecen solución incluso a variantes con demanda estocástica haciendo uso de redes neuronales. Se evaluó la incidencia de cada parámetro en la minimización de la función objetivo, así como el desempeño del algoritmo haciendo uso de instancias de la literatura ya solucionadas de 55, 80 y 200 nodos tomadas del Set A (Augerat,1995) y el Set M (Christofides, Mingozzi and Toth, 1979) y se obtuvo como resultado que el algoritmo propuesto brinda soluciones cercanas al óptimo a instancias de mediano tamaño, y en intervalos cortos de tiempo, logrando una relación de al menos 1.27 para la solución propuesta sobre la solución óptima.