A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands. (November 2018)

• Record Type: Journal Article
• Authors: Gutierrez, Andres; Dieulle, Laurence; Labadie, Nacima; Velasco, Nubia
• Is Part Of: Computers & operations research. Volume 99(2018)
• Page Start: 135
• Page End: 147
• Publication Date: 2018-11
• Subjects: Vehicle routing -- Stochastic programming -- Stochastic demands -- Hybrid metaheuristic -- Memetic algorithm -- Greedy randomized adaptive search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.06.012
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A hybrid MA-GRASP is proposed to solve the VRPSD. The effect of adding the GRASP is assessed proving that it improves the results quality. The proposed method outperforms the state of the art metaheuristics. The MA+GRASP efficiently solves big instances in small computational times. A new testbed with larger instances is proposed for testing future comparisons. Abstract: This article deals with the Vehicle Routing Problem with Stochastic Demands. To solve this problem, a hybrid metaheuristic combining a Memetic Algorithm and Greedy Randomized Adaptive Search Procedure is designed. The developed approach is tested on a 40 instances benchmark. The results are validated by comparing them to state of the art metaheuristics, they show that our method outperforms these metaheuristics in terms of quality and efficiency. A new testbed of 39 instances with up to 385 customers is also proposed and tested. This paper is the first one to deal with closer to real life size problems.