Program > By speaker > Bach Lukas

In recent years the computational capacity of the Graphics Processing Unit (GPU) in ordinary desktop computers has increased significantly compared to the Central Processing Unit (CPU). It is interesting to explore how this alternative source of computing power can be utilized. Most investigations of GPU-based solution methods in discrete optimization are based on swarm intelligence or evolutionary algorithms.

One of the best single-solution metaheuristics for discrete optimization is Adaptive Large Neighborhood Search (ALNS). GPU parallelization of ALNS has not been reported in the literature. We investigate ALNS on the GPU by developing a data parallel ALNS algorithm for the Distance-constrained Capacitated Vehicle Routing Problem (DCVRP). To achieve good utilization of the GPU, it was necessary to adapt the set of destroy and repair operators of a state-of-the-art CPU implementation.

The data parallel ALNS is implemented in NVIDIA CUDA. The Performance of a state-of-the-art CPU implementation and our GPU version is compared experimentally on an Intel Core i7-4770K with 3.5 GHz and an NVIDIA GeForce GTX TITAN. We use three standard DCVRP benchmarks: the Christofides, Mingozzi, and Toth instances, the Kelly instances, and the Li, Golden, and Wasil instances – in total a set of 46 instances with the number of customers ranging from 50 to 1200. On average, our GPU implementation of ALNS yields competitive solution quality with less runtime than the CPU implementation. However, on larger instances it is easier to utilize the parallelism of the GPU and achieve both improved solution quality and considerably improved runtime.