Skip to Main content Skip to Navigation
Book sections

A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem

Abstract : This chapter proposes new VRP heuristics based on Iterated Local Search (ILS): a pure ILS, a version with several offspring solutions per generation, called Evolutionary Local Search or ELS, and hybrid forms GRASP×ILS and GRASP×ELS. These variants share three main features: a simple structure, an alternation between solutions encoded as giant tours and VRP solutions, and a fast local search based on a sequential decomposition of moves. The proposed methods are tested on the Christofides et al. (1979) and Golden et al. (1998) instances. Our best algorithm is the GRASP×ELS hybrid. On the first set, if only one run with the same parameters is allowed, it outperforms all recent heuristics except the AGES algorithm of Mester and Bräysy (2007). Only AGES and the SEPAS method of Tarantilis (2005) do better on the second set, but GRASP×ELS improves two best-known solutions. Our algorithm is also faster than most VRP metaheuristics.
Complete list of metadata
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Wednesday, February 12, 2020 - 3:32:42 PM
Last modification on : Sunday, June 26, 2022 - 1:38:31 AM

Links full text





Christian Prins. A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem. Bio-inspired Algorithms for the Vehicle Routing Problem, 161, Springer Berlin Heidelberg, pp.35-53, 2009, Studies in Computational Intelligence, ⟨10.1007/978-3-540-85152-3_2⟩. ⟨hal-02476253⟩



Record views