Abstract
We investigate the efficiency of Adaptive Large Neighborhood Search (ALNS) on the Graphics Processing Unit (GPU). We do this by implementing an ALNS algorithm for the Distance-constrained Capacitated Vehicle Routing Problem (DCVRP) on a GPU. We benchmark towards a state of the art sequential implementation of an ALNS algorithm by Pisinger and Ropke [1].
In recent years the computational capacity of the GPU in ordinary desktop computers has increased significantly compared to the Central Processing Unit (CPU) normally used for computations. Hence, we find it interesting to investigate how this additional processing power is best utilized. A survey of GPU computing for routing problems can be found in Schulz, Hasle, Brodtkorb, and Hagen [2]. They find that most routing related GPU implementations use swarm intelligence, evolutionary, or local search based algorithms. To the best of our knowledge, there are no papers on ALNS implementations on a GPU.
ALNS consists of a neighborhood search where destroy operators remove parts of an existing solution and repair operators that reinsert them. There are multiple destroy and repair operators and these are selected probabilistically based on their merit. A new solution is accepted according to an overall metaheuristic. Our ALNS algorithm for the GPU is implemented using NVIDIAs CUDA C/C++ programming language. Compared to the CPU based implementation from Pisinger and Ropke [1], it is necessary to adapt some of the operators to achieve a good utilization of the GPU. In these cases we implement a GPU version of the operator mimicking the behavior of the CPU version.
Experiments are performed on an Intel Core i7-4770K with 3.5 GHz and an NVIDIA GeForce GTX TITAN. We perform tests on three sets of instances of the DCVRP: the Christofides, Mingozzi, and Toth instances, the Kelly instances, and the Li, Golden, and Wasil instances. In total this yields a set of 46 instances with the number of customers ranging from 50 to 1200. Our experiments show that, on average, our GPU implementation is close to the performance of the Pisinger and Ropke algorithm in terms of quality, but with less runtime.
References
[1] David Pisinger, and Stefan Ropke, A general heuristic for vehicle routing problems, Computers& Operations Research 34, 2403-2435 (2007)
[2] Christian Schulz, Geir Hasle, Andre R. Brodtkorb, and Trond R. Hagen, GPU computing in discrete optimization. Part II: Survey focused on routing problems, EURO Journal on Transportation and Logistics 2, 159-186 (2013)
In recent years the computational capacity of the GPU in ordinary desktop computers has increased significantly compared to the Central Processing Unit (CPU) normally used for computations. Hence, we find it interesting to investigate how this additional processing power is best utilized. A survey of GPU computing for routing problems can be found in Schulz, Hasle, Brodtkorb, and Hagen [2]. They find that most routing related GPU implementations use swarm intelligence, evolutionary, or local search based algorithms. To the best of our knowledge, there are no papers on ALNS implementations on a GPU.
ALNS consists of a neighborhood search where destroy operators remove parts of an existing solution and repair operators that reinsert them. There are multiple destroy and repair operators and these are selected probabilistically based on their merit. A new solution is accepted according to an overall metaheuristic. Our ALNS algorithm for the GPU is implemented using NVIDIAs CUDA C/C++ programming language. Compared to the CPU based implementation from Pisinger and Ropke [1], it is necessary to adapt some of the operators to achieve a good utilization of the GPU. In these cases we implement a GPU version of the operator mimicking the behavior of the CPU version.
Experiments are performed on an Intel Core i7-4770K with 3.5 GHz and an NVIDIA GeForce GTX TITAN. We perform tests on three sets of instances of the DCVRP: the Christofides, Mingozzi, and Toth instances, the Kelly instances, and the Li, Golden, and Wasil instances. In total this yields a set of 46 instances with the number of customers ranging from 50 to 1200. Our experiments show that, on average, our GPU implementation is close to the performance of the Pisinger and Ropke algorithm in terms of quality, but with less runtime.
References
[1] David Pisinger, and Stefan Ropke, A general heuristic for vehicle routing problems, Computers& Operations Research 34, 2403-2435 (2007)
[2] Christian Schulz, Geir Hasle, Andre R. Brodtkorb, and Trond R. Hagen, GPU computing in discrete optimization. Part II: Survey focused on routing problems, EURO Journal on Transportation and Logistics 2, 159-186 (2013)