A Parallel Genetic Algorithm with GPU Accelerated for Large-scale MDVRP in Emergency Logistics

Making an efficient and effective decision for Vehicle Routing Problem is one of the key issues in emergency logistics. While, as the majority of them are large-scale Multi-Depot VRPs, the computing time of finding a rational solution is often too long to meet the requirements of emergency management. So how to accelerate the algorithm becomes very important in solving this problem. In this paper, we proposed a parallel Genetic Algorithm (GA) with Graphics Processing Unit (GPU) accelerated. By assigning the computing tasks for each chromosome to independent threads, the algorithm can process all the operations in GA in parallel. Experimental results show that our parallel algorithm can reduce the computing time of MDVRP to a large degree, which can improve the efficiency and effectiveness of the decision-making process.