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 metadatas

https://hal-utt.archives-ouvertes.fr/hal-02476253
Contributor : Daniel Gavrysiak <>
Submitted on : Wednesday, February 12, 2020 - 3:32:42 PM
Last modification on : Thursday, February 13, 2020 - 1:34:57 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

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⟩

Share

Metrics

Record views

36