Offline approximate value iteration for dynamic solutions to the multivehicle routing problem with stochastic demand

The multivehicle routing problem with stochastic demand (MVRPSD) is an important issue both in theory and practice. However, solving the MVRPSD through traditional methods, such as a priori optimization or rollout-algorithm-based dynamic programming is generally limited by the issues of computation efficiency and solution quality. Under increasing demand for efficient real-time logistics, we propose a novel offline approximate value iteration (OAVI) algorithm for dynamic solutions to the MVRPSD. Our algorithm benefits from offline training and thus can provide fast and effective online dynamic routing solutions. Adopting such a novel and effective algorithm presents two challenges: first, we must define a proper cost structure for the dynamic routing decision; second, we must efficiently address the curse of dimensionality of the multivehicle problem. To solve these problems, we first describe the cost structure through the value function approximation (VFA) with basis functions involving a priori cost and a priori credibility; we then design two strategies, recourse reduction (RR) and neighborhood reduction (NR), to prune the action space. The numerical experiments show that our algorithm can substantially enhance computation efficiency and solution quality compared to traditional methods. • Dynamic solutions to the multivehicle routing problem with stochastic demand are studied. • An offline approximation value iteration algorithm is designed to solve the problem. • Basis function set and two pruning strategies are proposed to improve performance. • We analyze the algorithmic performance and application insights behind. • The algorithm proposed significantly outperforms the traditional method.