The Single Vehicle Routing Problem with Deliveries and Selective Pickups in a CPU-GPU Heterogeneous Environment

In this work, we propose a new algorithm to solve a variant of the Vehicle Routing Problem that is the Single Vehicle Routing Problem with Deliveries and Selective Pickups (SVRPDSP). Our algorithm produces good quality solutions that are better than the best known solutions in the literature. In order to reduce the time spent to solve large-sized instances, we also propose here a parallel implementation of our algorithm that explores a heterogeneous environment composed of a CPU and a GPU. Therefore, our algorithm harnesses the tremendous computing power of the GPU to improve the performance of the local searches computation. We obtained average speedups from 2.73 to 16.23 times with our parallel approach.