Skip to Main content Skip to Navigation
Book sections

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

Abstract : 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.
Document type :
Book sections
Complete list of metadatas
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 5:31:56 PM
Last modification on : Wednesday, March 4, 2020 - 12:28:05 PM

Links full text




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⟩



Record views