Adaptive Large Neighborhood Search using the Graphics Processing Unit

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), which we benchmark towards a state of the art sequential implementation by Pisinger and Ropke [1]. In recent years the computational capacity of the GPU in ordinary desktop computers has increased significantly compared to the CPU. In a survey, Schulz et al. [2] 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. A part of ALNS is a neighborhood search where destroy operators remove parts of an existing solution and repair operators reinserts them. Compared to the CPU based implementation, it is necessary to adapt some of the operators to achieve a good utilization of the GPU. We perform tests on well-known DCVRP instances. Our experiments show promising results. 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, André 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)