Un algoritmo rollout (ra) para la solución del problema de ruteo de vehículos con demanda estocástica, desde una perspectiva de reoptimización

Abstract

En el presente trabajo de investigación se presenta el Algoritmo Rollout de un solo paso (ORA) como una solución al Problema de Ruteo de Vehículo con Demanda Estocástica (VRPSD) con una perspectiva de reoptimización para el caso de único vehículo, el cual se centra en hallar una política mejorada que minimice el costo de la ruta resultante. Esto se obtiene por mejoras realizadas secuencialmente y de manera cíclica, teniendo como base una solución a priori hallada a través de la heurística Nearest Neighbor (NN). Se realizó un diseño de experimentos con el objetivo de analizar los efectos de la variación de los parámetros del algoritmo Rollout sobre la variable respuesta. Utilizando la propuesta de investigación realizada por Silvia Galván se ha construido un banco de pruebas, adaptando los factores y niveles al presente problema para validar el Algoritmo Rollout. Se validaron las soluciones obtenidas por el software y se medió la calidad de los resultados, los cuales fueron comparados con el método evolutivo de colonia de hormigas (EACO). A partir del resultado del diseño de experimentos se concluye que, el análisis del algoritmo se dividió para 4, 8 y 12 clientes. En los efectos estimados, para 4 y 8 clientes la ubicación de los clientes y la demanda promedio respectivamente, son factores significativos sobre la variable de respuesta. Para obtener mejores resultados sobre la función objetivo la ubicación de los clientes y la demanda promedio deben tomar el nivel 1 mientras que la desviación debe tomar el nivel 2. Los resultados obtenidos al comparar el Rollout con el método EACO muestran que el 37,5% de las instancias, para el algoritmo Rollout, arroja mejores resultados en el grupo de 8 y 12 clientes, con una diferencia porcentual mayor al 1%. 1