GPU-based distributed bee swarm optimisation for dynamic vehicle routing problem. (30th June 2019)

• Record Type: Journal Article
• Authors: Grid, Maroua; Djedi, NourEddine; Bitam, Salim
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 31:Number 3(2019)
• Page Start: 155
• Page End: 177
• Publication Date: 2019-06-30
• Subjects: DCVRP -- dynamic capacitated vehicle routing problem -- k-means -- parallel bees life algorithm -- P-BLA -- parallel optimisation -- GPGPU -- general purpose graphics processing units; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

Abstract

Nowadays, there is still a large gap between the requirements and the performance of decision support systems for many problems such as the vehicle routing problem, consists in conceiving a set of optimal routes for a fleet of vehicles, aiming at serving a given number of customers. Nevertheless, new customer orders could be introduced while a prior plan is in progress. Therefore, routes should be recalculated in a dynamic way. In this paper, we propose a new parallel combinatorial optimisation method based on graphic processing unit (GPU) called parallel bees life algorithm (P-BLA) to solve efficiency the dynamic capacitated vehicle routing problem (DCVRP) in terms of execution time, and to reduce computational complexity often considered as the major drawback of conventional optimisation methods. P-BLA is developed using CUDA framework performed on an island-based GPU. After a set of comparisons against conventional methods namely; genetic algorithm, ant system, Tabu search and sequential BLA, P-BLA has provided efficient results reached from the most tested DCVRP benchmarks.