A multi-population algorithm to solve the VRP with stochastic service and travel times

Abstract : The vehicle routing problem with stochastic travel and service times is a variant of vehicle routing problem where travel and service times are modeled as random variables. This paper addresses a version with hard time windows which is tackled by a mixed stochastic program with recourse and chance constraints. The recourse policy aims to deal with the costs generated when a customer time window is missed due to the stochastic nature of the problem. Moreover, the stochastic constraints guarantee a service level for each customer. A log-normal approximation is used to estimate the arrival times. The approximation considers previous customers failures to improve the estimation of the mean and variance of the arrival times. The problem is solved by means of a Multi-Population Memetic Algorithm (MPMA) and is tested on modified instances initially proposed for the deterministic problem. Furthermore, a comparison against related problems found in the literature is presented showing the performance of our solution approach. The results depict that the MPMA outperforms different methods with different types of objectives so demonstrating its efficiency and flexibility.