A Multi-thread GRASPxELS for the Heterogeneous Capacitated Vehicle Routing Problem - Archive ouverte HAL Access content directly
Book Sections Year : 2013

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

(1) , (2) , (1) , (2)
1
2

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.

Dates and versions

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

Identifiers

Cite

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⟩
19 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More