Single vehicle routing with stochastic demands : approximate dynamic programming

Abstract

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 ecient maintenance. The VFA+ reduces the computational time signicantly and still delivers high quality solutions. The signicant 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.