Article: GPU-based distributed bee swarm optimisation for dynamic vehicle routing problem Journal: International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC) 2019 Vol.31 No.3 pp.155 - 177 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. Inderscience Publishers - linking academia, business and industry through research

Title: GPU-based distributed bee swarm optimisation for dynamic vehicle routing problem

Authors: Maroua Grid; NourEddine Djedi; Salim Bitam

Addresses: LESIA Laboratory, Department of Computer Science, University of Biskra, P.O. Box 145 RP, Biskra 07000, Algeria ' LESIA Laboratory, Department of Computer Science, University of Biskra, P.O. Box 145 RP, Biskra 07000, Algeria ' LESIA Laboratory, Department of Computer Science, University of Biskra, P.O. Box 145 RP, Biskra 07000, Algeria

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.

Keywords: DCVRP; dynamic capacitated vehicle routing problem; k-means; parallel bees life algorithm; P-BLA; parallel optimisation; GPGPU; general purpose graphics processing units.

DOI: 10.1504/IJAHUC.2019.100734

International Journal of Ad Hoc and Ubiquitous Computing, 2019 Vol.31 No.3, pp.155 - 177

Received: 26 Jan 2017
Accepted: 27 Nov 2017
Published online: 17 Jul 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: GPU-based distributed bee swarm optimisation for dynamic vehicle routing problem

Keep up-to-date