Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02478120
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 5:16:52 PM
Last modification on : Wednesday, July 22, 2020 - 9:14:03 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Andres Gutierrez, Laurence Dieulle, Nacima Labadie, Nubia Velasco. A multi-population algorithm to solve the VRP with stochastic service and travel times. Computers and Industrial Engineering, Elsevier, 2018, 125, pp.144-156. ⟨10.1016/j.cie.2018.07.042⟩. ⟨hal-02478120⟩

Share

Metrics

Record views

38