A multi-population algorithm to solve the VRP with stochastic service and travel times. (November 2018)

• Record Type: Journal Article
• Authors: Gutierrez, Andres; Dieulle, Laurence; Labadie, Nacima; Velasco, Nubia
• Is Part Of: Computers & industrial engineering. Volume 125(2018)
• Page Start: 144
• Page End: 156
• Publication Date: 2018-11
• Subjects: Vehicle routing -- Stochastic programming -- Multi-population memetic algorithm -- Stochastic service and travel times -- Hard time windows; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.07.042
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A Multi-population Memetic Algorithm solves the VRPTW with stochastic times. A log-normal approximation to estimate arrival times is proposed. Comparisons between stochastic and deterministic approaches was made. Comparisons confirm the importance of considering uncertainties. The solution approach showed very competitive results. 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.