A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem - Archive ouverte HAL Access content directly
Book Sections Year : 2009

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

(1)
1

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.

Dates and versions

hal-02476253 , version 1 (12-02-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
12 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More