A Multi-thread GRASPxELS for the Heterogeneous Capacitated Vehicle Routing Problem - Université de technologie de Troyes Accéder directement au contenu
Chapitre D'ouvrage Année : 2013

A Multi-thread GRASPxELS for the Heterogeneous Capacitated Vehicle Routing Problem

Résumé

This chapter focuses on the definition of an efficient parallel metaheuristic which takes advantage of the multi-core design of recent processors. The approach is designed as a Greedy Randomized Adaptive Search Procedure (GRASP) hybridized with a multi-threaded version of an Evolutionary Local Search (ELS) metaheuristic scheme. Our approach is evaluated on an extension of the Vehicle Routing Problem where a heterogeneous fleet of vehicles is available to service a set of customers. The objective consists in designing a set of trips for a limited heterogeneous fleet of vehicles located at a depot node which minimizes the total transportation cost. Each type of vehicles is defined by a capacity and by the number of available vehicles. The efficiency of the parallel approach is evaluated on a new set of real-life instances built out of data from the French districts. A fair comparative study, using a same implementation, is done to evaluate the impact of the number of threads on the convergence rate. Thus, a better trade-off between solution quality and computational time can be reached. The numerical experiments show that the hybrid GRASPxparallel ELS outperforms the classical iterative version and provides numerous new best solutions.

Dates et versions

hal-02478156 , version 1 (13-02-2020)

Identifiants

Citer

Christophe Duhamel, Christophe Gouinaud, Philippe Lacomme, Caroline Prodhon. A Multi-thread GRASPxELS for the Heterogeneous Capacitated Vehicle Routing Problem. Hybrid Metaheuristics, 434, pp.237-269, 2013, Studies in Computational Intelligence, 978-3-642-30671-6. ⟨10.1007/978-3-642-30671-6_9⟩. ⟨hal-02478156⟩
29 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More