An efficient Parallel solution for the CVRP using k-NN, Matlab, and CUDA

Abstract

The nearest neighbor algorithm is analyzed to implement a solution to the Capacitated Vehicle Routing Problem (CVRP) to determine one or several routes of a fleet of vehicles with a specific load capacity. It is intended to take advantage of the power of GPUs to reduce the time needed to execute the algorithm significantly. The methodology implies a programming model and development scenarios. Firstly, the sequential nearest neighbor algorithm is analyzed to solve the CVRP, and its parallel implementation is discussed later. Matlab is used as a tool to implement CVRP and perform numerical and matrix calculations because it can interact with GPUs and CUDA. The effectiveness and efficiency of both implementations are tested in different CVRP instances in terms of execution time. The results indicate that parallel implementation is not just suitable but highly beneficial for large instances (greater than or equal to three hundred nodes).