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

摘要

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.