To main content

Adaptive Large Neighborhood Search using the Graphics Processing Unit

Adaptive Large Neighborhood Search using the Graphics Processing Unit

Category
Conference lecture and academic presentation
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), 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)
Client
  • Norges forskningsråd / 205298
  • Norges forskningsråd / 227071
  • Norges forskningsråd / 246825
Language
English
Author(s)
Affiliation
  • SINTEF Digital / Mathematics and Cybernetics
Presented at
EURO 2015 - 27th European Conference on Operational Research
Place
Glasgow
Date
11.07.2015 - 14.07.2015
Year
2015