Single vehicle routing with stochastic demands : approximate dynamic programming

This paper deals with the single vehicle routing problem with stochastic demands (VRPSD). We formulate a stochastic dynamic programming model and implement Approximate Dynamic Programming (ADP) algorithms to overcome the curses of dimensionality. The developed ADP algorithms are based on Value Function Approximations (VFA) with lookup table representation. The standard VFA algorithm is extended and improved for the VRPSD. In the improved VFA algorithm (VFA+), we consider a Q-learning algorithm with bounded lookup tables and efficient maintenance. The VFA+ reduces the computational time significantly and still delivers high quality solutions. The significant reduction in computational time enables solving larger scale instances, which is important for real-life decision making. Test instances found in the literature are used to validate and benchmark our obtained results.