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

Christian Prins (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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.

Mots clés: Local Search; Travelling Salesman Problem; Memetic Algorithm; Greedy Randomize Adaptive Search Procedure; Vehicle Route Problem

Domaines: Recherche opérationnelle [math.OC]; Algorithme et structure de données [cs.DS]

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⟩