A Heuristic Algorithm for the Vehicle Routing Problem with Stochastic Travel and Service Times

In this paper, we consider the vehicle routing problem with stochastic travel and service times. We determine the delivery routes that meet customer’s time window when the arrival time of the vehicle at customers is uncertain. We propose the algorithm that iteratively generates efficient routes and adds them as candidates. The algorithm adds multiple routes in one iteration to the possible routes, to improve computation time. The computational experiments show that the computation time can be significantly improved for the problem with many customers.