Model and algorithm for vehicle routing problem with spatial-temporal correlated stochastic travel times

Abstract:

This paper studies a version of vehicle routing problem with spatial-temporal correlated stochastic travel times in real road networks. First,a two-stage stochastic optimization model is established for this problem. An intelligent stochastic optimization method is then proposed to solve the model, in which an efficient intelligent optimization algorithm is developed to find candidate solutions, and the scenario generation technology is adopted to generate spatial-temporal correlated stochastic travel time scenarios to evaluate the solutions. This paper proposes a hybrid particle swarm optimization algorithm combined with a variable neighbourhood descent algorithm to perform effective optimization. Finally, a series of testing instances are established based on the road network of Beijing to verify the effectiveness of the hybrid particle swarm optimization algorithm. The experimental results show that considering the spatial-temporal correlation of stochastic vehicle travel times in real traffic environment will affect the best vehicle routing decisions.