A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands

Abstract

In this work we propose a hybrid dynamic programming evolutionary algorithm to solve the vehicle routing problem with stochastic demands, it is a well known NP-hard problem where uncertainty enhances the computational efforts required to obtain a feasible and near-optimal solution. We develop an evolutionary technique where a rollout dynamic programming algorithm is applied as local search method to improve the quality of solutions. Motivated by computational considerations, the rollout algorithm can be applied partially, so, this finds competitive solutions in large instances for which the global rollout dynamic programming strategy is time unfeasible.

Resumen. En este trabajo se propone un algoritmo evolutivo hibrido que combina un m ́etodo de programación dinámica estocástica para resolver el problema de enrutamiento de vehículos con demandas estocásticas, este es un problema demostrado como NP-difícil donde la presencia de incertidumbre incrementa los requerimientos computacionales necesarios para obtener soluciones factibles y cercanas a la óptima. Así, para el algoritmo evolutivo desarrollado se aplico un algoritmo rollout de programación dinámica estocástica como operador de búsqueda local para mejorar la calidad de las soluciones. Motivado por requerimientos computacionales, el algoritmo de rollout puede ser aplicado parcialmente, con el objetivo de encontrar soluciones competitivas en instancias lo suficientemente grandes para las cuales la estrategía global no es aplicable por consumir una cantidad de tiempo no tolerable.